Pagini recente » Cod sursa (job #2417008) | Cod sursa (job #1868825) | Cod sursa (job #1157145) | Cod sursa (job #2411932) | Cod sursa (job #1572637)
#include <stdio.h>
#include <string.h>
using namespace std;
FILE *fin = fopen("strmatch.in", "r");
FILE *fout = fopen("strmatch.out", "w");
char s[2000005], s2[2000005];
int pref[2000005], v[1024];
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] = ' ';
s[l + 1] = '\0';
s2[L + 1] = '\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;
}
}
// AFISARE
fprintf(fout, "%d\n", p);
if(p > 1000)
p = 1000;
for(i = 1; i <= p; i++)
fprintf(fout, "%d ", v[i]);
fprintf(fout, "\n");
return 0;
}