Pagini recente » Cod sursa (job #976291) | Cod sursa (job #1222227) | Cod sursa (job #668305) | Cod sursa (job #2394026) | Cod sursa (job #2245279)
#include <fstream>
#include <cstring>
#define Nmax 2000003
using namespace std;
char A[ Nmax ], B[ Nmax ];
int sol[ 1005 ], n, m, pi[ Nmax ], q, nr;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> (A + 1) >> (B + 1);
n = strlen( A + 1 );
m = strlen( B + 1 );
for ( int i = 2; i <= n; ++ i )
{
while ( q && (A[ i ] != A[ q + 1 ]) )
q = pi[ q ];
if ( A[ i ] == A[ q + 1 ] )
q ++;
pi[ i ] = q;
}
q = 0;
for ( int i = 1; i <= m; ++ i )
{
while ( q && (B[ i ] != A[ q + 1 ]) )
q = pi[ q ];
if ( B[ i ] == A[ q + 1 ] )
q ++;
if ( q == n )
{
if ( nr <= 1000 )
{
sol[ nr ] = i - n;
nr ++;
}
}
}
g << nr << "\n";
for ( int i = 0; i < nr; ++ i )
g << sol[ i ] << " ";
return 0;
}