Exceptional C++ Style 15)访问权限的使用
浏览数：21 /
时间：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;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
