Pagini recente » Cod sursa (job #3227164) | Cod sursa (job #2192710) | Cod sursa (job #685676) | Cod sursa (job #2606553) | Cod sursa (job #914310)
Cod sursa(job #914310)
#include <string.h>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <stdio.h>
#define MAX 2000000
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< pot.size(); i++) {
printf("%d ",pot[i]);
}
printf("\n");
return 0;
}