Pagini recente » Cod sursa (job #2382479) | Cod sursa (job #59731) | Cod sursa (job #2617062) | Cod sursa (job #3122084) | Cod sursa (job #2754894)
#include<iostream>
#include<fstream>
#include<cstring>
#define N 2000002
using namespace std;
int nr;
int poz[100];
int pi[N];
char s[N],t[N];
int* prefix(char *p ){
int i,n;
n=strlen(p);
int q=0;
pi[0]=0;
for(i=1;i<n;i++){
//q=pi[i-1];
while(q>0 && p[i]!=p[q]){
q=pi[q-1];
}
if(p[i]==p[q])
q++;
pi[i]=q;
}
return pi;
}
void kmp(char *p, char *s){
int *pi=prefix(p);
int q=0,i,n=strlen(s),m=strlen(p);
cout<<endl;
for(i=0;i<n;i++){
while(q>0 && s[i]!=p[q]){
q=pi[q-1];
}
if(s[i]==p[q])
q++;
if(q==m){
if(nr<100)
poz[nr]=i-m+1;
nr++;
q=pi[q-1];
}
}
}
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>s>>t;
kmp(s,t);
g<<nr<<endl;
for(int i=0;i<min(100,nr);i++)
g<<poz[i]<<" ";
g.close();
}