Pagini recente » Cod sursa (job #1399503) | Cod sursa (job #2102712) | Cod sursa (job #1241855) | Cod sursa (job #2842144) | Cod sursa (job #964567)
Cod sursa(job #964567)
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std ;
#define maxn 2000001
char S[maxn], W[maxn] ;
int T[maxn] ;
int lenS, lenW ;
vector<int> sol ;
void prefix()
{
T[0] = -1 ;
T[1] = 0 ;
int k = 0 ;
int poz = 2 ;
while( poz < lenW )
{
if( W[k] == W[ poz - 1 ] )
{
++k ;
T[poz] = k ;
++poz ;
}
else
{
if( k > 0 )
k = T[k] ;
else
{
T[poz] = 0 ;
++poz ;
}
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n", W);
scanf("%s", S);
lenS = strlen(S) ;
lenW = strlen(W) ;
prefix() ;
int poz = 0 ;
int start = 0 ;
while( poz + start < lenS )
{
if( W[poz] == S[ start + poz ] )
{
if( poz == lenW - 1 )
{
sol.push_back(start) ;
start = start + poz - T[poz] ;
if( T[poz] > -1 )
poz = T[poz] ;
else
poz = 0 ;
continue;
}
++poz ;
}
else
{
start = start + poz - T[poz] ;
if( T[poz] > -1 )
poz = T[poz] ;
else
poz = 0 ;
}
}
printf("%d\n", sol.size() );
for(size_t i = 0; i < sol.size() && i < 1000; ++i )
printf("%d ", sol[i]);
return 0 ;
}