Pagini recente » Cod sursa (job #1739594) | Cod sursa (job #2454676) | Cod sursa (job #286610) | Cod sursa (job #2916677) | Cod sursa (job #733128)
Cod sursa(job #733128)
#include <fstream>
#include <cstring>
#include <string>
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();
n=N.size();
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;
}
aux="";
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+1==n){
if(p>1000) i=m+7;
else pos[p++]=i-n+1;
}
}
fout<< p<<"\n";
for(i=0; i<p ; i++)
fout<<pos[i]<<' ';
return 0;
}