Pagini recente » Cod sursa (job #727193) | Cod sursa (job #2559388) | Cod sursa (job #2825480) | Cod sursa (job #2614497) | Cod sursa (job #710676)
Cod sursa(job #710676)
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir1[2000005], sir2[2000005];
int pi[2000005],pos[1024],n,m,i,q,nr;
inline void prefix()
{int i,q = 0;
pi[1] = 0;
for (i=2;i<=m;++i)
{ while (q && sir1[q+1] != sir1[i])
q = pi[q];
if (sir1[q+1] == sir1[i])
++q;
pi[i] = q;
}
}
int main()
{ fin >> sir1 >> sir2;
m = strlen(sir1);
n = strlen(sir2);
for (i=m+1;i>=1;--i)
sir1[i] = sir1[i-1];
for (i=n+1;i>=1;--i)
sir2[i] = sir2[i-1];
prefix();
for (i=1;i<=n;++i)
{ while (q && sir1[q+1] != sir2[i])
q = pi[q];
if (sir1[q+1] == sir2[i])
++q;
if (q == m)
{ q = pi[m];
++nr;
if (nr <= 1000)
pos[nr] = i-m;
}
}
fout << nr << '\n';
for (i=1;i<= min(nr,1000);++i)
fout << pos[i] << " ";
return 0;
}