Pagini recente » Cod sursa (job #1102786) | Cod sursa (job #571482) | Cod sursa (job #2989582) | Cod sursa (job #1735735) | Cod sursa (job #2245278)
#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 )
{
nr++;
if ( nr <= 1000 )
sol[ nr ] = i - n;
}
}
g << nr << endl;
for ( int i = 1; i <= nr; ++ i )
g << sol[ i ] << " ";
return 0;
}