Pagini recente » Cod sursa (job #2834296) | Cod sursa (job #1154280) | Cod sursa (job #2178329) | Cod sursa (job #3039373) | Cod sursa (job #2340364)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("strmatch.in");
ofstream out("strmatch.out");
const int NR = 2000005 ;
char s [ NR ] , t [ NR ] ;
int p [ NR ] , l , nrap , sol [ 1002 ] , i , n , m ;
int main()
{
in >> s + 1 ;
in >> t + 1 ;
n = strlen( s + 1 ) ;
m = strlen( t + 1 ) ;
p [ 1 ] = 0 ;
for ( i = 2 ; i <= n ; ++ i )
{
while ( l && s [ i ] != s [ l + 1 ] ) l = p [ l ] ;
if ( s [ i ] == s [ l + 1 ] ) l ++ ;
p [ i ] = l ;
}
l = 0 ;
for ( i = 1 ; i <= m ; ++ i )
{
while ( l && t [ i ] != s [ l + 1 ] ) l = p [ l ] ;
if ( t [ i ] == s [ l + 1 ] ) l ++ ;
if ( l == n )
{
nrap ++ ;
if ( nrap <= 1000 )
{
sol [ nrap ] = i - n ;
}
l = p [ l ] ;
}
}
out << nrap << '\n' ;
nrap = min ( nrap , 1000 ) ;
for ( i = 1 ; i <= nrap ; ++ i ) out << sol [ i ] << ' ' ;
return 0;
}