Pagini recente » Cod sursa (job #730274) | Cod sursa (job #2807405) | Cod sursa (job #3145354) | Cod sursa (job #1117456) | Cod sursa (job #2520288)
///strmatch infoarena
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 2000003;
char s[NMAX]; //string to search in
char w[NMAX]; //pattern to be searched
int pi[NMAX]; //pi array of word w
int mch=0; //number of matches
bool poz[NMAX]; //poz[i]=1 => there is a match at position i
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",w,s);
int n=strlen(s);
int m=strlen(w);
//make pi vector
int q=0;
for(int i=1;i<m;++i){
while(q && w[i]!=w[q])
q=pi[q-1];
if(w[i]==w[q])
++q;
pi[i]=q;
}
//compare pattern w with string s
q=0;
for(int i=0;i<n;++i){
while(q && s[i]!=w[q])
q=pi[q-1];
if(s[i]==w[q])
++q;
if(q==m){
q=pi[q-1];
mch++;
poz[i-m+1]=1;
}
}
//display
printf("%d\n",mch);
int cnt=0;
for(int i=0;i<n && cnt<1000;++i)
if(poz[i])
printf("%d ",i),cnt++;
return 0;
}