Eclipse搭建C/C++开发环境

浏览数：26 / 时间：2015年06月08日

利用kmp求next数组的思想对字符串进行模式匹配。

显而易见，最后一个字符的匹配到的位置到最后一个字符是一个循环节。

例如

匹配串： a b a c a b a c

next数组：0 1 1 2 1 2 3 4

第8个字符的next数组的值为4；

则一个循环节为8-4+1=4；

总共的循环次数为8/4=2次；

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
char str[1100000];
int next[1100000];
void chu()
{
    int i=0,j=-1;
    next[i]=j;
    int len=strlen(str);
    while(i<len)
    {
        if(j==-1||str[i]==str[j])
        {
            i++;j++;
            next[i]=j;
        }
        else j=next[j];
    }
    int k=len-j;
    if(len%k==0)
    {
        cout<<len/k<<endl;
    }
    else cout<<1<<endl;
}
int main()
{
    while(~scanf("%s",str))
    {
        if(str[0]==‘.‘)break;
        chu();
    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Eclipse搭建C/C++开发环境