Pagini recente » Cod sursa (job #3359164) | Cod sursa (job #3362866) | Cod sursa (job #3359154) | Cod sursa (job #3359168) | Cod sursa (job #3362867)
#include <iostream>
using namespace std;
const int MAXN = 2000000;
const int MAX = 1000;
char v[MAXN + 1];
int pi[MAXN];//pi[i] = lungimea maxima a sufixului care se termina in i egal cu prefixul(in afara de sufixul de marime i)
int vrez[MAX];
int main()
{
//kmp
FILE *fin, *fout;
int n, i, rez, j;
char ch;
fin = fopen("strmatch.in", "r");
ch = fgetc(fin);
n = 0;
while (ch != '\n') {
v[n] = ch;
n++;
ch = fgetc(fin);
}
v[n] = -1;//santinela
j = 0;
for (i = 1; i < n; i++) {
while (j > 0 && v[i] != v[j]) {
j = pi[j - 1];
}
if (v[i] == v[j]) {
j++;
}
pi[i] = j;
}
ch = fgetc(fin);
j = rez = i = 0;
while (ch != '\n' && ch != EOF) {
i++;
while (j > 0 && ch != v[j]) {
j = pi[j - 1];
}
if (ch == v[j]) {
j++;
}
if (j == n) {
if (rez < MAX) {
vrez[rez] = i - n;
}
rez++;
}
ch = fgetc(fin);
}
fclose(fin);
fout = fopen("strmatch.out", "w");
fprintf(fout, "%d\n", rez);
if (rez > MAX) {
rez = MAX;
}
for (i = 0; i < rez; i++) {
fprintf(fout, "%d ", vrez[i]);
}
fprintf(fout, "\n");
fclose(fout);
return 0;
}