Pagini recente » Cod sursa (job #2618259) | Cod sursa (job #1829243) | Cod sursa (job #964669) | Cod sursa (job #1464603) | Cod sursa (job #2805823)
#include <stdio.h>
#include <cstring>
using namespace std;
FILE* f, * g;
char x[2000002], y[2000002];
int n, m, ss, v[1004], pi[2000002];
void citire()
{
fscanf(f, "%s", x);
fscanf(f, "%s", y);
m = strlen(x) - 1;
n = strlen(y) - 1;
}
void kmp()
{
int k = -1, i;
pi[0] = -1;
for (i = 1;i <= m;i++)
{
while (k > -1 && x[k + 1] != x[i])
k = pi[k];
if (x[k + 1] == x[i])
k++;
pi[i] = k;
}
}
void kmp1()
{
int i, k = -1;
for (i = 0;i <= n;i++)
{
while (k > -1 && x[k + 1] != y[i])
k = pi[k];
if (y[i] == x[k + 1])
k++;
if (k == m)
{
ss++;
if (ss <= 1000)
v[ss] = i - k;
}
}
}
void afisare()
{
int i, mi = 1000;
/*for(i=1;i<=m;i++)
fprintf(g,"%d ",pi[i]);
fprintf(g,"\n");
*/
fprintf(g, "%d\n", ss);
if (ss < mi)
mi = ss;
for (i = 1;i <= mi;i++)
fprintf(g, "%d ", v[i]);
}
int main()
{
f = fopen("strmatch.in", "r");
g = fopen("strmatch.out", "w");
citire();
kmp();
kmp1();
afisare();
fclose(f);
fclose(g);
return 0;
}