Pagini recente » Cod sursa (job #2127161) | Cod sursa (job #2469991) | Cod sursa (job #295300) | Cod sursa (job #2639728) | Cod sursa (job #1364148)
#include <cstdio>
#include <cstring>
#include <vector>
#define Nmax 2000050
using namespace std;
char A[Nmax],B[Nmax];
int N,M,total,P[Nmax];
vector<int> sol;
void Read()
{
scanf("%s%s",A+1,B+1);
A[0] = '#';
B[0] = '#';
N = strlen(A+1);
M = strlen(B+1);
}
void KMP_Prefix()
{
int p = 0;
for(int i = 2; i <= N; ++i)
{
while(p && A[i] != A[p+1])
p = P[p];
if(A[i] == A[p+1])
++p;
P[i] = p;
}
}
void KMP_Match()
{
int p = 0;
for(int i = 1; i <= M; ++i)
{
while(p && B[i] != A[p+1])
p = P[p];
if(B[i] == A[p+1])
++p;
if(p == N){
if(total < 1000)
sol.push_back(i-N);
++total;
p = P[p];
}
}
}
void Solve()
{
KMP_Prefix();
KMP_Match();
printf("%d\n",total);
for(int i = 0; i < sol.size(); ++i)
printf("%d ",sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
Read();
Solve();
return 0;
}