Pagini recente » Cod sursa (job #1180060) | Cod sursa (job #2849015) | Cod sursa (job #3211321) | Cod sursa (job #2243821) | Cod sursa (job #1044698)
#include <fstream>
#include <string.h>
using namespace std;
char a[2000005], b[2000005];
int pi[2000005], c[2000005], s;
void prefix()
{
int n, i, k;
n = strlen(a)-1;
pi[1] = 0;
k = 0;
for (i = 2; i <= n; i++)
{
while (k > 0 && a[k + 1] != a[i])
k = pi[k];
if (a[k + 1] == a[i])k++;
pi[i] = k;
}
}
void KMP()
{
int n, m, q, i;
n = strlen(a)-1;
m = strlen(b)-1;
q = 0;
for (i = 1; i <= m; i++)
{
while (q > 0 && a[q + 1] != b[i])
q = pi[q];
if (a[q + 1] == b[i])q++;
if (q == n)
{
q = pi[n];
s++;
if (s <= 1000)
c[s] = i - n;
}
}
}
int main()
{
int i;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(a, 2000005, '\n');
f.getline(b, 2000005, '\n');
for (i = strlen(a); i >= 0; i--)a[i] = a[i - 1];
for (i = strlen(b); i >= 0; i--)b[i] = b[i - 1];
a[0] =' ';
b[0] =' ';
prefix();
KMP();
g << s << endl;
for ( i = 1; i <= s; i++)
g<< c[i] << " ";
return 0;
}