Pagini recente » Cod sursa (job #338279) | Cod sursa (job #2139982) | Cod sursa (job #2456299) | Cod sursa (job #46757) | Cod sursa (job #1647374)
#include <cstring>
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std ;
const int NMAX = 20000005 ;
int prefix[NMAX], sol, S[NMAX];
string A, B ;
inline void PREFIX()
{
int K = 0 ;
prefix[1] = 0 ;
for(int i = 2 ; i < A.size(); ++ i)
{
while(K > 0 && A[i] != A[K + 1])
K = prefix[K] ;
if(A[i] == A[K + 1])
K ++ ;
prefix[i] = K ;
}
}
inline void KMP()
{
int Q = 0 ;
for(int i = 1 ; i < B.size() ; ++ i)
{
while(Q && B[i] != A[Q + 1])
Q = prefix[Q] ;
if(A[Q + 1] == B[i])
Q ++ ;
if(Q == A.size() -1)
{
Q = prefix[Q] ;
sol ++ ;
if(sol <= 1000)
{
S[sol] = i - A.size() + 1 ;
}
}
}
}
int main()
{
freopen ("strmatch.in", "r", stdin) ;
freopen ("strmatch.out", "w", stdout) ;
cin >> A >> B ;
A.push_back(' ') ;
B.push_back(' ') ;
for(int i = A.size() - 1 ; i >= 0 ; -- i)
A[i + 1] = A[i] ;
for(int i = B.size() - 1 ; i >= 0 ; -- i)
B[i + 1] = B[i] ;
A[0] = ' ' ;
B[0] = ' ' ;
PREFIX() ;
KMP() ;
cout << sol << '\n' ;
for(int i = 1 ; i <= min(sol, 1000) ; ++i)
cout << S[i] << ' ' ;
}