Pagini recente » Cod sursa (job #2555164) | Cod sursa (job #2779207) | Cod sursa (job #795483) | Cod sursa (job #23474) | Cod sursa (job #710667)
Cod sursa(job #710667)
#include<fstream>
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[i] = 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);
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;
for (i = 1; i <= min(nr,1000); ++i)
fout << pos[i];
return 0;
}