poj 3461 Oulipo（kmp统计子串出现次数）

题意：统计子串出现在主串中的次数

思路：典型kmp

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

int next[];

void GetNext(char t[]){//求next数组

    int j,k,len;

    j=;

    k=-;

    next[]=-;

    len=strlen(t);

    while(j<len){

        if(k==-||t[j]==t[k]){

            ++j;

            ++k;

            next[j]=k;//此句可由优化替代

            /*优化（仅保证求KMPIndex时可用。谨慎使用。）

            if(t[j]!=t[k])next[j]=k;

            else next[j]=next[k];

            */

        }

        else k=next[k];

    }

}

int KMPIndex(char s[],char t[]){//求子串首次出现在主串中的位置

    int i,j,lens,lent;

    i=j=;

    lens=strlen(s);

    lent=strlen(t);

    while(i<lens&&j<lent){

        if(j==-||s[i]==t[j]){

            ++i;

            ++j;

        }

        else j=next[j];

    }

    if(j>=lent)return i-lent;

    else return -;

}

int KMPCount(char s[],char t[]){//统计子串在主串中的出现次数，可重叠

    int i,j,lens,lent,cnt;

    i=j=;

    lens=strlen(s);

    lent=strlen(t);

    cnt=;

    while(i<lens){

        if(j==-||s[i]==t[j]){

            ++i;

            ++j;

        }

        else j=next[j];

        if(j==lent)++cnt;

    }

    return cnt;

}

void KMPCount2(char t[]){//统计单串中从某个位置以前有多少重复的串

    int i,lent,tmp;

    lent=strlen(t);

    for(i=;i<=lent;++i){

        tmp=i-next[i];

        if(i%tmp==&&i/tmp>)

            printf("\t位置：%d 个数：%d\n",i,i/tmp);

    }

}

int main(){

    char str1[],str2[];

    int i;

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%s%s",str2,str1);

        GetNext(str2);//求子串的next数组

        printf("%d\n",KMPCount(str1,str2));

    }

    return ;

}