Pagini recente » Cod sursa (job #1923031) | Cod sursa (job #999850) | Cod sursa (job #780816) | Cod sursa (job #3032242) | Cod sursa (job #1647409)
#include <cstring>
#include <cstdio>
#include <fstream>
#include <queue>
using namespace std ;
const int NMAX = 2000005 ;
int prefix[NMAX], sol, S[NMAX];
char A[NMAX] ;
char B[NMAX] ;
inline void PREFIX()
{
int K = 0 ;
prefix[1] = 0 ;
for(int i = 2 ; i < strlen(A) ; ++ 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 < strlen(B) ; ++ i)
{
while(Q && B[i] != A[Q + 1])
Q = prefix[Q] ;
if(A[Q + 1] == B[i])
Q ++ ;
if(Q == strlen(A) - 1)
{
Q = prefix[Q] ;
sol ++ ;
if(sol <= 1000)
{
S[sol] = i - strlen(A) + 1 ;
}
}
}
}
ifstream fin("strmatch.in") ;
ofstream fout("strmatch.out") ;
int main()
{
fin.getline(A, NMAX) ;
fin.getline(B, NMAX) ;
for(int i = strlen(A) - 1 ; i >= 0 ; -- i)
A[i + 1] = A[i] ;
for(int i = strlen(B) - 1 ; i >= 0 ; -- i)
B[i + 1] = B[i] ;
A[0] = ' ' ;
B[0] = ' ' ;
PREFIX() ;
KMP() ;
fout << sol << '\n' ;
for(int i = 1 ; i <= min(sol, 1000) ; ++i)
fout << S[i] << ' ' ;
}