Pagini recente » Cod sursa (job #1188060) | Cod sursa (job #562288) | Cod sursa (job #727933) | Cod sursa (job #1387596) | Cod sursa (job #531301)
Cod sursa(job #531301)
#include <iostream>
#include <math.h>
#define N 2000005
using namespace std;
char A[N],B[N];
int sir[1005];
int pi[N];
int n;
void computePI() {
int lung = strlen(A);
int k = 0;
for(int i = 1; i <= lung; i++) {
while (k != 0 && A[k] != A[i])
k = pi[k - 1];
if (A[k] == A[i])
k++;
pi[i] = k;
}
}
int min(int a,int b) {
if (a > b) return b;
return a;
}
void kmp() {
int lung = strlen(B);
int n = strlen(A);
int k = 0;
for(int i = 0; i < lung; i++) {
while (k > 0 && A[k] != B[i])
k = pi[k-1];
if (A[k] == B[i]) k++;
if (k == n) {
sir[0]++;
if (sir[0] <= 1000)
sir[sir[0]] = i - k + 1;
k = pi[k - 1];
}
}
}
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&A);
scanf("%s",&B);
computePI();
kmp();
printf("%d\n",sir[0]);
for(int i = 1; i <= min(sir[0],1000); i++)
printf("%d ",sir[i]);
return 0;
}