Pagini recente » Cod sursa (job #3162647) | Cod sursa (job #232525) | Cod sursa (job #1357439) | Cod sursa (job #652582) | Cod sursa (job #724238)
Cod sursa(job #724238)
#include<fstream>
using namespace std;
ifstream fi( "strmatch.in" );
ofstream fo( "strmatch.out" );
int M,N,pi[2000000],pos[1024];
char A[2000000],B[2000000],c;
int main()
{int i, q = 0, n = 0;
while ( (c=fi.get()) && (c!='\n') )
A[++M]=c;
while ( (c=fi.get()) && (c!='\n') && (c!=EOF) )
B[++N]=c;
for (i = 2, pi[1] = 0; i <= M; ++i)
{
while (q && A[q+1] != A[i])
q = pi[q];
if (A[q+1] == A[i])
++q;
pi[i] = q;
}for (i = 1; i <= N; ++i)
{
while (q && A[q+1] != B[i])
q = pi[q];
if (A[q+1] == B[i])
++q;
if (q == M)
{
q = pi[M];
++n;
if (n <= 1000)
pos[n] = i-M;
}}fo<<n<<'\n';
if( n> 1000 )
n=1000;
for ( i=1; i<=n; i++ )
fo<<pos[i]<<' ';
fi.close();
fo.close();
}