KMP poj

题目来自：http://www.cnblogs.com/wuyiqi/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 = -1;
    next[0] = -1;
    int j = 0;
    int len = strlen(str);
    while(j < len){
        if(k == -1 || 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-8;
const double Pi = 4 * atan(1.0);
const int MAXN =  1000000 + 10;
const long long MOD =  1000000007;
const int dr[] = {1,0,-1,0,-1,1,-1,1};
const int dc[] = {0,1,0,-1,1,-1,-1,1};
typedef long long LL;

LL gac(LL a,LL b){
    return b?gac(b,a%b):a;
}
char str[10000+10];
char str1[MAXN];
int next[10000+10];

void getNext(){
    int k = -1;
    int j = 0;
    next[0] = -1;
    int len = strlen(str);
    while(j < len){
        if(k == -1 || 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 = 0;
        int len = strlen(str);
        int len1 = strlen(str1);
        int j = 0;
        int i = 0;
        while(i < len1){
            if(j == -1 || str[j] == str1[i]){
                i++;
                j++;
            }
            else{
                j = next[j];
            }
            if(j == len){
                cnt++;
            }
        }
        printf("%d
",cnt);
    }
    return 0;
}

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 + 10;
const int ESP = 10e-8;

char str[MAXN];
int next[MAXN];

void getNext(){
    int k = -1;
    next[0] = -1;
    int j = 0;
    int len = strlen(str);
    while(j < len){
        if(k == -1 || 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[0] == '.')
            break;
        getNext();
        int len = strlen(str);
        if(len % (len - next[len]) == 0){
            printf("%d
",len / (len - next[len]));
        }
        else{
            printf("1
");
        }
    }
    return 0;
}

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 = 400000 + 10;
const int ESP = 10e-8;

char str[MAXN];
int next[MAXN];
int q[MAXN];

void getNext(){
    int k = -1;
    next[0] = -1;
    int j = 0;
    int len = strlen(str);
    while(j < len){
        if(k == -1 || 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,0,sizeof(next));
        getNext();
        int len = strlen(str);
        int cnt = 0;
        int k = next[len];
        q[cnt++] = len;
        while(k){
            q[cnt++] = k;
            k = next[k];
        }
        for(int i = cnt-1;i >= 0;i--){
            if(i != cnt-1)
                cout << ' ';
            cout << q[i];
        }
        cout << endl;
    }
    return 0;
}

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-8;
const double Pi = 4 * atan(1.0);
const int MAXN =  10000 + 10;
const long long MOD =  1000000007;
const int dr[] = {1,0,-1,0,-1,1,-1,1};
const int dc[] = {0,1,0,-1,1,-1,-1,1};
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][80];
int next[MAXN];
int n,m;

void getR(int i){
    int j = 0;
    int k = -1;
    next[0] = -1;
    while(j < m){
        if(k == -1 || str[i][j] == str[i][k]){
            j++;
            k++;
            next[j] = k;
        }
        else{
            k = next[k];
        }
    }
}

void getC(int i){
    int j = 0;
    int k = -1;
    next[0] = -1;
    while(j < n){
        if(k == -1 || 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 = 0;i < n;i++){
            scanf("%s",str[i]);
        }
        int r = 1;
        int c = 1;
        for(int i = 0;i < n;i++){
            getR(i);
            int t = m - next[m];
            r = lcm(r,t);
            if(r >= m){
                r = m;
                break;
            }
        }
        for(int i = 0;i < m;i++){
            getC(i);
            int t = n - next[n];
            c = lcm(c,t);
            if(c >= n){
                c = n;
                break;
            }
        }

        printf("%d
",r*c);
    }
    return 0;
}

http://poj.org/problem?id=3080

求给出字符串共同拥有的字典序最小的长度最长的子串

解题思路：暴力，strstr函数直接水掉……2333333

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

char dna[11][70];
char str[70];
char str1[70];

int main()
{
   //  freopen("input.in","r",stdin);
    int t;
    int m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&m);
        for(int i = 0;i < m;i++)
            scanf("%s",dna[i]);
        int maxnum = -0xfffff;
        int len = strlen(dna[0]);
        bool flag = true;
        for(int i = 0;i < len;i++)
        {
            memset(str,0,sizeof(str));
            int t = 0;
            for(int j = 0;j < len;j++)
            {
                bool flag2 = true;
                if(i+j >= len)
                    break;
                str[j] = dna[0][i+j];
                for(int k = 1;k < m;k++)
                {
                    if(strstr(dna[k],str) == NULL)
                    {
                        flag2 = false;
                        break;
                    }
                }
                if(flag2)
                {
                    t++;
                    if(t == maxnum)
                    {
                        if(strcmp(str1,str) > 0)
                            strcpy(str1,str);
                    }
                    if(t > maxnum)
                    {
                        maxnum = t;
                        strcpy(str1,str);
                    }
                    flag = false;
                }
                else
                    break;
            }
        }
        if(maxnum < 3 || flag)
            printf("no significant commonalities
");
        else
        {
            printf("%s
",str1);
        }
    }
    return 0;
}