题目来自：http://www.cnblogs.com/*qi/archive/2012/01/06/2315188.html
KMP算法开始是判断字符串b是否是字符串a的子串，朴素的算法是枚举，时间复杂度O(m*n)
然后KMP(三个人名字的缩写)发明了KMP算法使时间复杂度降到了O(m+n)
但是<string.h>里面明明有一个函数是strstr(a,b)判断b是否为a的子串啊啊啊啊！！！
这个写得蛮好：http://blog.chinaunix.net/uid-27164517-id-3280128.html
以下仅限于个人理解：
a和b字符串匹配过程中，在j位置开始不匹配了
在0-j中寻找b0 b1 b2 ... bk = b(j-1-k) ... b(j-1)
当b与a字符串失配b应当从k+1个字符开始与a中刚刚失配的位置进行匹配
所以要确定k的值，而k的取值仅与j的位置有关，所以用next[]数组来盛放相应位置k的值
next(j) = -1 起始位置
k+1 0 <= k < j-1 失配时b应当重新开始匹配的位置
0 其他
next[]数组的确立
void getNext(){
int k = -;
next[] = -;
int j = ;
int len = strlen(str);
while(j < len){
if(k == - || str[j] == str[k]){
k++;
j++;
next[j] = k;
}
else{
k = next[k];
}
}
}
http://poj.org/problem?id=3461
给a串和b串，求出b串中包含多少个a串
主要思路:
先对b进行next求解，然后对匹配到达最后进行计数……
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#include <map>
#include <set> using namespace std; const int INF = 0xffffff;
const double ESP = 10e-;
const double Pi = * atan(1.0);
const int MAXN = + ;
const long long MOD = ;
const int dr[] = {,,-,,-,,-,};
const int dc[] = {,,,-,,-,-,};
typedef long long LL; LL gac(LL a,LL b){
return b?gac(b,a%b):a;
}
char str[+];
char str1[MAXN];
int next[+]; void getNext(){
int k = -;
int j = ;
next[] = -;
int len = strlen(str);
while(j < len){
if(k == - || str[j] == str[k]){
j++;
k++;
next[j] = k;
}
else{
k = next[k];
}
}
} int main()
{
#ifndef ONLINE_JUDGE
freopen("inpt.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
int t;
scanf("%d",&t);
while(t--){
scanf("%s%s",str,str1);
getNext();
int cnt = ;
int len = strlen(str);
int len1 = strlen(str1);
int j = ;
int i = ;
while(i < len1){
if(j == - || str[j] == str1[i]){
i++;
j++;
}
else{
j = next[j];
}
if(j == len){
cnt++;
}
}
printf("%d\n",cnt);
}
return ;
}
http://poj.org/problem?id=2406
给你一个字符串s要求求出最大的 n 使 s = a^n (a是字串)
主要思路：
先对s串进行next求解，然后如果 len % (len-next[len]) == 0说明字符串恰由子串的n次方组成
则结果是 len / (len-next[len])
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm> using namespace std;
const int MAXN = 10e6 + ;
const int ESP = 10e-; char str[MAXN];
int next[MAXN]; void getNext(){
int k = -;
next[] = -;
int j = ;
int len = strlen(str);
while(j < len){
if(k == - || str[j] == str[k]){
k++;
j++;
next[j] = k;
}
else{
k = next[k];
}
}
} int main(){
// freopen("input.txt","r",stdin);
while(~scanf("%s",str)){
if(str[] == '.')
break;
getNext();
int len = strlen(str);
if(len % (len - next[len]) == ){
printf("%d\n",len / (len - next[len]));
}
else{
printf("1\n");
}
}
return ;
}
http://poj.org/problem?id=2752
给你一个字符串s，要求求出字符串从头开始到某个位置形成的子串a和从后面的某个位置到结尾的子串b，完全相同时输出a串的长度
主要思路：
先对s串进行next求解，从结尾开始依次寻找next[j] != 0 这说明最后几个和开头肯定是相同的，所以最后输出就好，ps：s串本身也符合条件
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm> using namespace std;
const int MAXN = + ;
const int ESP = 10e-; char str[MAXN];
int next[MAXN];
int q[MAXN]; void getNext(){
int k = -;
next[] = -;
int j = ;
int len = strlen(str);
while(j < len){
if(k == - || str[j] == str[k]){
k++;
j++;
next[j] = k;
}
else{
k = next[k];
}
}
} int main(){
// freopen("input.txt","r",stdin);
while(~scanf("%s",str)){
memset(next,,sizeof(next));
getNext();
int len = strlen(str);
int cnt = ;
int k = next[len];
q[cnt++] = len;
while(k){
q[cnt++] = k;
k = next[k];
}
for(int i = cnt-;i >= ;i--){
if(i != cnt-)
cout << ' ';
cout << q[i];
}
cout << endl;
}
return ;
}
http://poj.org/problem?id=2185
给你一个字符串矩阵，求出最小的子矩阵能把矩阵完全覆盖，求其面积
主要思路：
对字符矩阵的每行，每列进行next求解，求得其最小的字串能把所代表的字符串覆盖掉，得到行的最小公倍数，和列的最小公倍数，然后相乘求出面积。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#include <map>
#include <set> using namespace std; const int INF = 0xffffff;
const double ESP = 10e-;
const double Pi = * atan(1.0);
const int MAXN = + ;
const long long MOD = ;
const int dr[] = {,,-,,-,,-,};
const int dc[] = {,,,-,,-,-,};
typedef long long LL; LL gac(LL a,LL b){
return b?gac(b,a%b):a;
}
int lcm(int i,int j){
return i * j / gac(i,j);
}
char str[MAXN][];
int next[MAXN];
int n,m; void getR(int i){
int j = ;
int k = -;
next[] = -;
while(j < m){
if(k == - || str[i][j] == str[i][k]){
j++;
k++;
next[j] = k;
}
else{
k = next[k];
}
}
} void getC(int i){
int j = ;
int k = -;
next[] = -;
while(j < n){
if(k == - || str[j][i] == str[k][i]){
j++;
k++;
next[j] = k;
}
else{ k = next[k];
}
}
} int main()
{
#ifndef ONLINE_JUDGE
freopen("inpt.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
while(~scanf("%d%d",&n,&m)){
for(int i = ;i < n;i++){
scanf("%s",str[i]);
}
int r = ;
int c = ;
for(int i = ;i < n;i++){
getR(i);
int t = m - next[m];
r = lcm(r,t);
if(r >= m){
r = m;
break;
}
}
for(int i = ;i < m;i++){
getC(i);
int t = n - next[n];
c = lcm(c,t);
if(c >= n){
c = n;
break;
}
} printf("%d\n",r*c);
}
return ;
}
http://poj.org/problem?id=3080
求给出字符串共同拥有的字典序最小的长度最长的子串
解题思路：暴力，strstr函数直接水掉……2333333
#include <iostream>
#include <cstring>
#include <cstdio> using namespace std; char dna[][];
char str[];
char str1[]; int main()
{
// freopen("input.in","r",stdin);
int t;
int m;
scanf("%d",&t);
while(t--)
{
scanf("%d",&m);
for(int i = ;i < m;i++)
scanf("%s",dna[i]);
int maxnum = -0xfffff;
int len = strlen(dna[]);
bool flag = true;
for(int i = ;i < len;i++)
{
memset(str,,sizeof(str));
int t = ;
for(int j = ;j < len;j++)
{
bool flag2 = true;
if(i+j >= len)
break;
str[j] = dna[][i+j];
for(int k = ;k < m;k++)
{
if(strstr(dna[k],str) == NULL)
{
flag2 = false;
break;
}
}
if(flag2)
{
t++;
if(t == maxnum)
{
if(strcmp(str1,str) > )
strcpy(str1,str);
}
if(t > maxnum)
{
maxnum = t;
strcpy(str1,str);
}
flag = false;
}
else
break;
}
}
if(maxnum < || flag)
printf("no significant commonalities\n");
else
{
printf("%s\n",str1);
}
}
return ;
}