Pagini recente » Cod sursa (job #1423129) | Cod sursa (job #851753) | Cod sursa (job #1310064) | Cod sursa (job #2382161) | Cod sursa (job #1546687)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
int z[2000002],n,st,dr,sol[20000],k,m;
char v[2000002],v2[2000002];
ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );
int main()
{
fin.getline( v2 , 20000 );
fin.getline( v , 200000 );
//fout << v2;
//fout << endl;
//fout << v;
//fout << endl;
n = strlen( v2 );
k = strlen ( v );
strcat( v2 , "*" );
strcat( v2 , v );
//fout << v2 << endl;
m = strlen( v2 );
for ( int i=n; i<m; ++i )
{
if ( dr >= i )
{
z[i] = min( dr - i + 1 , z[i - st] );
}
while ( v2[z[i]] == v2[ i + z[i]] )
{
++z[i];
}
if ( i + z[i] - 1 > dr )
{
dr = i + z[i] - 1;
st = i;
}
}
k = 0;
for ( int i = n; i < m; ++i )
{
if ( z[i] == n )
{
++k;
sol[k] = i - n - 1;
}
}
fout << k << endl;
for ( int i = 1; i <= k; ++i )
fout << sol[i] << ' ';
return 0;
}