Description
求子串的next值，用next数组存放。所有输出
Input
输入一个字符串
Output
输出全部next值
Sample Input
abaabcac
Sample Output
0 1 1 2 2 3 1 2
#include <iostream>
#include <cstring>
using namespace std;
int main(){
char s[100];
cin>>s;
int suffix[100];
int len=strlen(s);
int pos=0;
suffix[0]=-1;
suffix[1]=0;
for(int i=2;i<=len;++i){
while(pos>=0&&s[pos]!=s[i-1])
pos=suffix[pos];
suffix[i]=++pos;
}
int i=1;
cout<<suffix[0]+1;
while(i<strlen(s)){
cout<<' '<<suffix[i]+1;
i++;
}
return 0;
}
Description
输入一个主串和一个子串，用KMP进行匹配，问进行几趟匹配才成功，若没成功，则输出0
Input
输入一个主串和一个子串
Output
匹配的趟数
Sample Input
ababcabcacbab abcac
Sample Output
3
#include <iostream>
#include <cstring>
using namespace std;
int main(){
char s[100];
char b[100];
cin>>b;
cin>>s;
int suffix[100];
int len=strlen(s);
int pos=0;
suffix[0]=-1;
suffix[1]=0;
for(int i=2;i<=len;++i){
while(pos>=0&&s[pos]!=s[i-1])
pos=suffix[pos];
suffix[i]=++pos;
}
int i=0,j=0;
int cns=1;
bool flag=false;
while(i<strlen(b))
if(b[i]==s[j]){
j++;
i++;
if(s[j]=='\0'){
flag=true;
break;
}
}
else if(suffix[j]==-1){
i++;
j=0;
cns++;
}
else {
j=suffix[j];
cns++;
}
if(flag)cout<<cns<<'\12';
else cout<<0<<'\12';
return 0;
}
Description
输入一个主串和一个子串，若匹配成功，则找出匹配的趟数和在子串在主串中的位置，若匹配不成功，则输出0
Input
输入两个字符串
Output
输出匹配的趟数和位置
Sample Input
ababcabcacbab abcac
Sample Output
3 6
#include <iostream>
#include <cstring>
using namespace std;
int main(){
char s[100];
char b[100];
cin>>b;
cin>>s;
int suffix[100];
int len=strlen(s);
int pos=0;
suffix[0]=-1;
suffix[1]=0;
for(int i=2;i<=len;++i){
while(pos>=0&&s[pos]!=s[i-1])
pos=suffix[pos];
suffix[i]=++pos;
}
int i=0,j=0;
int cns=1;
bool flag=false;
while(i<strlen(b))
if(b[i]==s[j]){
j++;
i++;
if(s[j]=='\0'){
flag=true;
break;
}
}
else if(suffix[j]==-1){
i++;
j=0;
cns++;
}
else {
j=suffix[j];
cns++;
}
//cout<<"i "<<i<<" j "<<j<<" len "<<strlen(b)<<'\12';
if(flag)cout<<cns<<' '<<i-j+1<<'\12';
else cout<<0<<'\12';
return 0;
}
版权声明：本文为博主原创文章。未经博主同意不得转载。
举报
举报
- 本文已收录于下面专栏：
0条评论
objective-c
Delphi
Ruby
PHP
C#
C++
JavaScript
Visual Basic
Python
Java
CSS
SQL
其他