kmp入門小結

void get_next(char *s)
{int len = strlen(s);int j = 0; int k = -1;while (j < len){if (k == -1 || s[j] == s[k]){j++; k++; next[j] = k;}else k = next[k];}
}

設t = next[i]; next[i] 表示的是 i之前最大的t滿足 s[0...t-1] ?= ?s[i-t...i-1]

比如 0123 4 0123 5 ，next[9] = 4.

結論：len - next[len] 為最小覆蓋子串。

Poj3461?Oulipo

題意：給出兩個串，問第二個串在第一個串中出現的次數

/* ***********************************************Author        : 一個西瓜Mail          : 879447570@qq.comCreated Time  : 2015-04-07 16:24:21Problem       : Oulipo
************************************************ */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std; 
#define INF 1000000000
//typedef __int64 LL; const int maxn = 11111;
int next[maxn];
char str[maxn];
char str1[maxn*100];void get_next(char *s)
{next[0] = -1;int j = 0 ;int k = -1;int len = strlen(s);while(j<len){if(k==-1||s[j]==s[k]){j++;k++;next[j] = k;}else k = next[k];}
}int gao(char *s1,char *s2)
{int ans = 0;int len1 = strlen(s1);int len2 =strlen(s2);int j = -1;int k = -1;while(j<len2){if(k==-1||s1[k]==s2[j]){j++;k++;//printf("%d %d\n",j,k);
        }else k = next[k];if(k==len1){ans++;k = next[k];}}return ans;
}int main()
{int T;cin>>T;while(T--){cin>>str;cin>>str1;get_next(str);int k = gao(str,str1);cout<<k<<endl;}return 0;
}

Poj1961?Period

就用到上面那個結論了

/* ***********************************************Author        : 一個西瓜Mail          : 879447570@qq.comCreated Time  : 2015-04-07 17:50:15Problem       : Period
************************************************ */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std; 
#define INF 1000000000
//typedef __int64 LL; const int maxn = 1111111;
int next[maxn];
char str[maxn];
void get_next(char *s)
{int len =strlen(s);int j = 0;int k = -1;next[0] = -1;while(j<len){if(k==-1||s[j]==s[k]){j++;k++; next[j] = k;}else k = next[k];}
}int main()
{int Icase = 0 ;int n;while(scanf("%d",&n)&&n){if(Icase) cout<<endl;printf("Test case #%d\n",++Icase);scanf("%s",str);get_next(str);int len = strlen(str); for(int i = 1;i<len;i++){int t = i+1;if(t%(t - next[t])==0&&(t/(t-next[t])!=1)){printf("%d %d\n",t,t/(t - next[t]));}}}return 0;
}

Poj2752?Seek the Name, Seek the Fame

給出一個串，問哪些既是前綴，又是后綴。

next數組不就是，到當前串的第i個位置，既是這個子串的前綴又是后綴的最長前綴么。迭代下去求就行了。

/* ***********************************************Author        : 一個西瓜Mail          : 879447570@qq.comCreated Time  : 2015-04-07 17:28:12Problem       : Seek the Name, Seek the Fame
************************************************ */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std; 
#define INF 1000000000
//typedef __int64 LL; const int maxn = 4*1e5 +10;
int next[maxn];
char str[maxn];void get_next(char *s)
{next[0] = -1;int len =strlen(s);int j = 0 ;int k = -1;while(j<len){if(k==-1||s[j]==s[k]){j++;k++;next[j] =  k;}else k = next[k];}
}
vector<int> q;
int main()
{while(scanf("%s",str)!=EOF){get_next(str);q.clear();int k = strlen(str);q.push_back(k);k = next[k];while(k){q.push_back(k);k = next[k];}for(int i = q.size() - 1;i>=0;i--){printf("%d ",q[i]);}cout<<endl;}return 0;
}

Poj2406?Power Strings

和1961一樣的。

/* ***********************************************Author        : 一個西瓜Mail          : 879447570@qq.comCreated Time  : 2015-04-07 17:50:40Problem       : Power Strings
************************************************ */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std; 
#define INF 1000000000
//typedef __int64 LL; const int maxn = 1e6+10;
char str[maxn];
int next[maxn];void get_next(char *s)
{int len =strlen(s);int j = 0 ;int k = -1;next[0] = -1;while(j<len){if(k==-1||s[j]==s[k]){j++;k++; next[j] = k;}else k = next[k];}
}int main() {while(cin>>str){if(str[0]=='.') break;get_next(str);int len = strlen(str);if(len%(len-next[len])==0)cout<<len / (len - next[len])<<endl;else cout<<1<<endl;}return 0; 
}

?