Pagini recente » Cod sursa (job #976860) | Cod sursa (job #1361628) | Cod sursa (job #2990895) | Cod sursa (job #1059656) | Cod sursa (job #1628809)
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;
int n, m, rez[nmax];
char P[nmax], S[nmax];
int prefix[nmax];
void preprocessPattern()
{
int a = 0;
prefix[1] = 0;
for (int i = 2; i <= m; i++)
{
while (a > 0 && P[a + 1] != P[i])
{
a = prefix[a];
}
if (P[a + 1] == P[i])
a++;
prefix[i] = a;
}
}
void kmp()
{
int a = 0;
for (int i = 1; i <= n; i++)
{
while (a > 0 && P[a + 1] != S[i]) a = prefix[a];
if (P[a + 1] == S[i]) a++;
if (a == m)
{
rez[ ++rez[0] ] = i - m;
a = prefix[a];
}
}
}
int main()
{
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
fi >> (P+1);
fi >> (S+1);
m = int(strlen(P + 1));
n = int(strlen(S + 1));
preprocessPattern();
kmp();
fo << rez[0] << "\n";
for (int i = 1; i <= min(1000, rez[0]); i++)
fo << rez[i] << " ";
fi.close();
fo.close();
return 0;
}