Pagini recente » Cod sursa (job #123925) | Cod sursa (job #2633468) | Cod sursa (job #466568) | Cod sursa (job #1593364) | Cod sursa (job #1830968)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define NMAX 2000005
using namespace std;
char A[NMAX], B[NMAX];
int P[NMAX], N;
vector<int> R;
void read()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n", A + 1);
scanf("%s" , B + 1);
A[0] = ' ';
B[0] = ' ';
}
void patternArray()
{
int len_A = strlen(A);
P[1] = 0;
for(int i = 1, j = 2; i < len_A && j < len_A; i++)
{
if(A[i] == A[j])
{
P[i] = P[i - 1] + 1;
j++;
}
else
{
while(j != 1)
{
if(A[j] == A[i])
{
P[i] = j;
j++;
break;
}
else
{
j = P[j - 1] + 1;
}
}
if(j == 1)
{
P[i] = 0;
}
}
}
}
void KMP()
{
int len_A = strlen(A);
int len_B = strlen(B);
for(int i = 1, j = 1; i < len_B; i++)
{
if(B[i] == A[j])
{
j++;
if(j == len_A)
{
j = P[j - 1] + 1;
R.push_back(i - len_A + 1);
}
}
else
{
j = P[j - 1] + 1;
}
}
}
void print()
{
int len_R = min((int)R.size(), 1000);
printf("%d\n", len_R);
for(int i = 0; i < len_R; i++)
printf("%d ", R[i]);
}
int main()
{
read();
patternArray();
KMP();
print();
return 0;
}