Pagini recente » Cod sursa (job #2247563) | Cod sursa (job #879738) | Cod sursa (job #1354980) | Cod sursa (job #2697005) | Cod sursa (job #2754915)
#include<iostream>
#include<fstream>
#include<cstring>
#define N 2000002
#define NR_POZ 1000
using namespace std;
int nr;
int poz[NR_POZ];
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<NR_POZ)
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(NR_POZ,nr);i++)
g<<poz[i]<<" ";
g.close();
}