Pagini recente » Cod sursa (job #1645486) | Cod sursa (job #819749) | Cod sursa (job #1661197) | Cod sursa (job #3266853) | Cod sursa (job #1167488)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,pi[2000011],k,nr;
char N[2000011],M[2000011];
int sol[1011];
int main(void){
register int i,j;
f>>N+1>>M+1;
n=strlen(N+1),m=strlen(M+1);
for(i=2;i<=n;i++){
while(k>0 && N[k+1]!=N[i])
k=pi[k];
if(N[k+1]==N[i]) k++;
pi[i]=k;
}
k=0;
for(i=1;i<=m+1;i++){
while(k>0 && N[k+1]!=M[i])
k=pi[k];
if(N[k+1]==M[i]) k++;
if(k==n){
k=pi[k];
sol[++nr]=i-n;
}
}
g<<nr<<"\n";
nr=(nr>1000?1000:nr);
for(i=1;i<=nr;i++) g<<sol[i]<<" ";
f.close();
g.close();
return 0;
}