Pagini recente » Cod sursa (job #2834566) | Cod sursa (job #1187385) | Cod sursa (job #2414064) | Cod sursa (job #532920) | Cod sursa (job #1998707)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000001],B[2000001];
int n,m;
int urm[2000001];
vector <int> V;
void urmatorul()
{
int k=-1;
urm[0]=0;
for(int x=1;x<m;++x)
{
while(k>0 && A[k+1]!=A[x]) k=urm[k];
if(A[k+1]==A[x]) k++;
urm[x]=k;
}
}
int main()
{ int x=-1;
f.getline(A,2000001);
f.getline(B,2000001);
n=strlen(B);
m=strlen(A);
urmatorul();
for(int i=0;i<n;++i)
{
while(x>0 && A[x+1]!=B[i]) x=urm[x];
if(A[x+1]==B[i]) x++;
if(x==m-1)
{
V.push_back(i-m+1);
x=urm[x];
}
}
g<<V.size()<<'\n';
for(int i=0;i<V.size();++i)
g<<V[i]<<" ";
return 0;
}