@hsxrr
2017-02-26T12:17:38.000000Z
字数 5298
阅读 691
字符串 kmp
A - 最小表示法
题目
选择一个字符串中的某一个字符作为开始字符，使得这个新的字符串字典序最小，问这个字符选取在数组的第几位
思路
暴力匹配即可
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
using namespace std;
const int N = 2e4+7;
char s[N];
int pd_s(){
int len = strlen(s),i,k,j;
for( i = 0 , k = 1 , j = 0; i < len && k < len && j < len ;){
if( s[(i+j)%len] == s[(k+j)%len] ){
j++;
//continue;
}else{
if( s[(i+j)%len] > s[(k+j)%len] ){
i = k++;
//continue;
}else{
k++;
//continue;
}
j = 0;
}
}
return i;
}
int main(){
int t;
scanf("%d",&t);
while( t-- ){
scanf("%s",s);
printf("%d\n",pd_s()+1);
}
return 0;
}
题意
给你两个字符串a,b，strlen(b) > strlen(a)，问b中含有多少串a，部分重叠的也算一串
思路
KMP匹配，匹配成功继续匹配，计数值加一
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
using namespace std;
const int N = 1e6+7;
const int M = 1e4+7;
char s1[M],s2[N];
int s1_next[M];
void getnext(){
int len = strlen(s1);
s1_next[0] = -1;
int j = 0 , k = -1;
while( j < len )
if( k == -1 || s1[k] == s1[j] ) k++ , j++ , s1_next[j] = k;
else k = s1_next[k];
}
int KMP_match(){
int i = 0,j = 0,len = strlen(s2) , lenans = strlen(s1) , ans = 0;
getnext();
while( i < len ){
if( j == -1 || s2[i] == s1[j] )
i++,j++;
else
j = s1_next[j];
if( j == lenans ){
ans++;
j = s1_next[j];
}
}
return ans;
}
int main(){
int t;
scanf("%d",&t);
while( t-- ){
scanf("%s%s",s1,s2);
printf("%d\n",KMP_match());
}
return 0;
}
题意
对于给定数字，数字的最后一位可以放到第一位，问把此操作循环一遍以后得到的所有数字中大于原本数字的，等于原本数字的，小于原本数字的有多少个？
思路
扩展kmp算法，先字符串自己增长一倍，然后算数next数组算出最长公共前缀，然后匹配i与next,匹配的时候对于第i个匹配直接匹配是s[i+next[i]] 与 s[next[i]]即为两串字符串第一处不同的地方，如果相同，当前next[i] == strlen(未增长前的s),匹配到第一次i+next[i] > strlen(未增长前的s)既要结束匹配，否则就多计算了
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
using namespace std;
const int N = 1e5+7;
char s[N] , s1[N*2];
int nt[N] , extend[N];
void getnext(char *T){
int a = 0;
int Tlen = strlen(T);
nt[0] = Tlen;
while( a < Tlen-1 && T[a] == T[a+1] ) a++;
nt[1] = a;
a = 1;
for(int k = 2 ; k < Tlen ; k++){
int p = a + nt[a] - 1 , L = nt[k-a];
if( k+L > p ){
int j = (p-k+1) > 0 ? p-k+1:0;
while( k+j<Tlen && T[k+j] == T[j] )
j++;
nt[k] = j;
a = k;
}else nt[k] = L;
}
}
void build( char *S , char *T ){
int len = strlen(S);
for(int i = 0 ; i < len ; i++){
T[i] = T[i+len] = S[i];
}
T[len*2-1] = '\0';
}
int main(){
int t,kase = 0;
scanf("%d",&t);
while( t-- ){
scanf("%s",s);
build(s,s1);
getnext(s1);
int len = strlen(s) , a = 0 , b = 0 , c = 0 , k;
for(int i = 1; i <= len ; i++){
if( i + nt[i] >= len ){
k = len % i ? len : i;
break;
}
}
for(int i = 0 ; i < k ; i++){
if( nt[i] >= len ) b++;
else if( nt[i] >= 0 ){
if( s1[i+nt[i]] > s[nt[i]] ) c++;
else a++;
}
}
printf("Case %d: %d %d %d\n",++kase,a,b,c);
}
return 0;
}
题意
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
思路
把单词拆分成一个个字母，然后用树形结构存下这些字母，并且每一层记录其本层拥有的单词数目
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
using namespace std;
const int N = 26;
struct Tree{
Tree *next[N];
int v;
Tree(){
v = 0;
memset(next,NULL,sizeof(next));
}
};
char s[12];
Tree *root = new Tree();
void creatTree(char str[]){
int len = strlen(str);
Tree *p = root , *q;
for(int i = 0 ; i < len ; i++){
int id = str[i] - 'a';
if( p->next[id] == NULL )
p->next[id] = new Tree();
p = p->next[id];
p->v++;
}
}
int findTrie(char str[]){
int len = strlen(str);
Tree *p = root;
for(int i = 0 ; i < len ; i++){
int id = str[i] - 'a';
if( p->next[id] == NULL ) return 0;
p = p->next[id];
}
return p->v;
}
int main(){
for(int i = 0 ; i < N ; i++){
root->next[i] = NULL;
}
while( true ){
gets(s);
if( s[0] == '\0' ) break;
creatTree(s);
}
while( scanf("%s",s) != EOF )
printf("%d\n",findTrie(s));
return 0;
}
题意
求给定字符串最长的回文子串长度
思路
把字符串每个字符之间插入一个特殊字符'#',头部加入'$',尾部插入'\0'，这时候所有的回文子串都是aba类型的，只需要假定每个字符是回文串的中心，由这个字符串出发左右伸展，只到匹配失败，但是暴力匹配会超时，这是记录下之前的回文串最远到达的地方和这个字符串的中心位置，这是次匹配都可以对比这个最远的位置，如果在最远的位置里面，那么这里的开始匹配区域就可以直接去这个位置与中心位置对称位置已经匹配好的长度开始匹配，从而大大降低了时间复杂度
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <set>
#include <map>
using namespace std;
const int N = 1e6+7;
const int M = 1e4+7;
char s[N] , str[N*2];
int p[N*2];
int solve(){
int maxn = 0,i = 0;
int len = strlen(s) , slen = 2*len+3;
str[0] = '$';
str[1] = '#';
for(;i<len;i++){
str[i*2+2] = s[i];
str[i*2+3] = '#';
p[2*i+2] = p[2*i+3] = 0;
}
p[0] = p[1] = p[2*len+2] = p[2*len+3] = 0;
str[slen-1] = '\0';
int id = 0;
for(i = 1; i < slen ; i++){
if( maxn > i )
p[i] = min(p[2*id-i],p[id]+id-i);
else
p[i] = 1;
for(; str[i+p[i]] == str[i-p[i]];p[i]++);
if( p[i] + i > maxn ){
maxn = p[i] + i;
id = i;
}
}
maxn = 0;
for(i = 1 ; i < slen ; i++)
if( maxn < p[i]-1 )
maxn = p[i] - 1;
return maxn;
}
int main(){
char op[10] = "END";
int kase = 0;
while( scanf("%s",s) != EOF ){
if( strcmp(s,op) == 0 ) break;
printf("Case %d: %d\n",++kase,solve());
}
return 0;
}
题意
把一个字符串用哈夫曼编码得到一串二进制表示，以减小储存空间，而储存空间的安全值是m，如果超过空间限制就是不安全的，先给你字符串和安全值，问你字符串能否安全存储
思路
把所有字符出现的频率压入一个优先队列中，每次抽取最小的两个，分别编码为0，1，然后加起来放回队列中，只到队列中只剩一个元素的时候结束，编码总存储空间即为最小消耗存储空间，但要注意特判只有一个字符的情况
AC代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5+7;
const int M = 30;
const int INF = 0x3f3f3f3f;
struct node{
int t;
bool operator <(const node & rhs) const{
return t > rhs.t;
}
};
char s[N];
int ans[M];
priority_queue<node> pq;
int main(){
int n,m;
node temp;
while( scanf("%d",&n) != EOF ){
while( n-- ){
scanf("%d%s",&m,s);
while( !pq.empty() ) pq.pop();
int len = strlen(s);
memset(ans,0,sizeof(ans));
for(int i = 0 ; i < len ; i++)
ans[s[i]-'a'+1]++;
for(int i = 0 ; i < M ; i++)
if( ans[i] ){
temp.t =ans[i];
pq.push(temp);
}
int count = 0 ,min1;
if( pq.size() == 1 ){
temp = pq.top();
if( temp.t <= m ) printf("yes\n");
else printf("no\n");
continue;
}
while( !pq.empty() ){
if( pq.size() == 1 ){
break;
}else{
temp = pq.top();pq.pop();
min1 = temp.t;
temp = pq.top();pq.pop();
min1 += temp.t;
count += min1;
temp.t = min1;
pq.push(temp);
}
}
//printf("count = %d , m = %d\n",count,m);
if( count > m ) printf("no\n");
else printf("yes\n");
}
}
return 0;
}