Pagini recente » Cod sursa (job #2343434) | Cod sursa (job #2716912) | Cod sursa (job #51580) | Cod sursa (job #2091821) | Cod sursa (job #914313)
Cod sursa(job #914313)
#include <string.h>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <stdio.h>
#define MAX 2000010
using namespace std;
vector <int> pot, tab;
char smic[MAX], smare[MAX];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i, j, pos, lmi, lma, cand;
scanf("%s", smic);
scanf("%s", smare);
lmi = strlen(smic);
lma = strlen(smare);
tab.resize(lmi);
tab[0] = -1;
cand = -1;
for (i = 1; i < lmi; i++) {
if (smic[i] == smic[cand+1]) {
cand++;
tab[i] = cand;
}
else {
if (cand >= 0) {
cand = tab[cand];
i--;
}
else if (cand == -1)
tab[i] = -1;
}
}
j = 0;
for (i = 0; i < lma; i++) {
if (smic[j] == smare[i]) {
j++;
if (j == lmi) {
pot.push_back(i-j+1);
j = tab[j-1]+1;
}
}
else
j = tab[j-1]+1;
}
printf("%d\n", pot.size());
int max = 1000;
if (max > pot.size())
max = pot.size();
for (i = 0; i< max; i++) {
printf("%d ",pot[i]);
}
printf("\n");
return 0;
}