Pagini recente » Cod sursa (job #2863847) | Cod sursa (job #2361025) | Cod sursa (job #3175792) | Cod sursa (job #2482292) | Cod sursa (job #1805824)
#include <cstdio>
#include <vector>
using namespace std;
const int maxLen = 2000000;
char A[maxLen + 1 + maxLen + 1];
int pref[maxLen + 1 + maxLen + 1];
vector<int> pos;
void kmp_pref(char* w, int* pref) {
int l = strlen(w);
pref[0] = 0;
for(int i = 1; i < l; ++ i) {
int x = pref[i - 1];
while(x > 0 and w[i] != w[x])
x = pref[x - 1];
if(w[i] == w[x])
pref[i] = x + 1;
else
pref[i] = 0;
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(A);
int l = strlen(A);
A[l] = '*';
gets(A + l + 1);
kmp_pref(A, pref);
for(int i = 0; A[i] != '\0'; ++ i)
if(pref[i] == l)
pos.push_back(i - l - l);
unsigned k = pos.size();
printf("%u\n", k);
if(k > 1000)
k = 1000;
for(int i = 0; i < k; ++ i)
printf("%d ", pos[i]);
printf("\n");
return 0;
}