Pagini recente » Cod sursa (job #1312852) | Cod sursa (job #2027110) | Cod sursa (job #1909561) | Cod sursa (job #1274184) | Cod sursa (job #2910475)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin ("strmatch.in") ;
ofstream cout ("strmatch.out") ;
char a[200002],b[2000002];
int p[2000002], v[1002] ;
int nr,m,n,l ;
void read()
{
cin >> a + 1 ;
cin >> b + 1 ;
n=strlen (a+1);
m=strlen (b+1);
p[1] = 0;
}
void first()
{
l = 0 ;
for ( int i = 2 ; i <= n ; i ++ )
{
while ( l != 0 && a[i] != a[l+1] )
l = p[l] ;
if ( a[i] == a[l+1] )
l ++ ;
p[i] = l ;
}
}
void second()
{
l = 0 ;
for (int i = 1 ; i <= m ; i ++ )
{
while ( l != 0 && b[i] != a[l+1] )
l = p[l] ;
if ( b[i] == a[l+1] )
l ++ ;
if ( l == n )
{
nr ++ ;
if ( nr <= 1000 )
v[nr] = i - n ;
l = p[l] ;
}
}
}
void print ()
{
cout << nr << "\n" ;
nr = min ( nr, 1000) ;
for ( int i = 1 ; i <= nr ; i ++ )
cout<<v[i]<<" " ;
}
int main()
{
read() ;
first() ;
second() ;
print() ;
return 0;
}