Pagini recente » Cod sursa (job #2944097) | Cod sursa (job #2054825) | Cod sursa (job #1698732) | Cod sursa (job #374649) | Cod sursa (job #1572171)
#include <stdio.h>
#include <string.h>
using namespace std;
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
char s[2000001], s2[2000001];
int pref[2000001], v[2000001];
int main(){
int i, j, l, L, q = 0, p = 0;
char c;
fscanf(fin, "%s", s);
fscanf(fin, "%c", &c);
fscanf(fin, "%s", s2);
l = strlen(s);
L = strlen(s2);
for(i = l; i > 0; i--)
s[i] = s[i - 1];
for(i = L; i > 0; i--)
s2[i] = s2[i - 1];
s[0] = ' ';
s2[0] = ' ';
// GENERAREA PREFIXELOR
i = 0;
for(j = 2; j <= l; j++){
while(i > 0 && s[i + 1] != s[j])
i = pref[i];
if(s[i + 1] == s[j])
i++;
pref[j] = i;
}
//KMP
for(i = 1; i <= L; i++){
while(q > 0 && s[q + 1] != s2[i])
q = pref[q];
if(s[q + 1] == s2[i])
q++;
if(q == l){
q = pref[l];
p++;
v[p] = i - l;
}
}
fprintf(fout, "%d\n", p);
for(i = 1; i <= p; i++)
fprintf(fout, "%d ", v[i]);
return 0;
}