Pagini recente » Cod sursa (job #586489) | Cod sursa (job #112766) | Profil ankaramessi | Cod sursa (job #2481737) | Cod sursa (job #1632356)
#include <fstream>
#include <cstring>
using namespace std;
const int NMAX = 2000005 ;
ifstream fin("strmacth.in") ;
ofstream fout("strmacth.out") ;
char A[NMAX], B[NMAX] ;
int N, M, pi[NMAX], K, sol, SOL[NMAX];
inline void Prefix()
{
N = strlen(A) - 1 ;
K = 0 ;
for(int i = 2 ; i <= N ; ++ i)
{
while(K > 0 && A[K + 1] != A[i])
K = pi[K] ;
if(A[K + 1] == A[i])
K = K + 1 ;
pi[i] = K ;
}
}
inline void MATCH()
{
M = strlen(B) - 1 ;
N = strlen(A) - 1;
K = 0 ;
for(int i = 1 ; i <= M ; ++ i)
{
while(K > 0 && A[K + 1] != B[i])
K = pi[K] ;
if(A[K + 1] == B[i])
K = K + 1 ;
if(K == N)
{
sol ++ ;
if(sol < 1001)
SOL[sol] = i - N ;
K = 0 ;
}
}
}
int main()
{
fin >> A >> B ;
Prefix() ;
MATCH() ;
fout << sol << '\n' ;
for(int i = 1 ; i <= sol ; ++ i)
fout << SOL[i] << ' ' ;
fin.close() ;
fout.close() ;
return 0;
}