Pagini recente » Rusuoaica | Diferente pentru concursuri intre reviziile 138 si 139 | Diferente pentru documentatie/textile intre reviziile 64 si 107 | Diferente pentru preoni-2006/runda-1/solutii intre reviziile 15 si 26 | Cod sursa (job #2245280)
#include <fstream>
#include <cstring>
#include <list>
#include <utility>
#define Nmax 2000003
using namespace std;
char A[ Nmax ], B[ Nmax ];
int n, m, pi[ Nmax ], q, nr;
list <int> sol;
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.push_back( i - n );
}
}
g << nr << "\n";
for ( list<int>::iterator it = sol.begin(); it != sol.end(); it ++ )
g << *it << " ";
return 0;
}