Pagini recente » Cod sursa (job #2622911) | Cod sursa (job #3135810) | Cod sursa (job #1123610) | Cod sursa (job #2099988) | Cod sursa (job #733147)
Cod sursa(job #733147)
#include <fstream>
#include <cstring>
#include <string>
#include <iostream>
#define fout cout
using namespace std;
int main(){
string N,M,aux;
int n,m,pi[2000002],k;
int pos[1000],p=0;
int i,q;
ifstream fin("strmatch.in");
//ofstream fout("strmatch.out");
fin>>aux; N=" "+aux;
fin>>aux; M=" "+aux;
m=M.size()-1;
n=N.size()-1;
for(pi[1]=0, k=0, 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;
}
for(q=0,i=1;i<=m;i++){
while(q>0 && N[q+1]!=M[i])
q=pi[q];
if(N[q+1]==M[i])
q++;
if(q==n){
if(p<1000)
pos[p]=i-n;
p++;
//q=pi[n];
}
}
fout<< p<<"\n";
for(i=0; i<p ; i++)
fout<<pos[i]<<' ';
return 0;
}