Pagini recente » Cod sursa (job #2970004) | Cod sursa (job #84386) | Cod sursa (job #3189724) | Cod sursa (job #1219067) | Cod sursa (job #899486)
Cod sursa(job #899486)
#include <fstream>
#include <cstring>
using namespace std;
// Knuth-Morris-Pratt
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int maxn = 2000002;
char A[maxn], B[maxn];
int F[maxn], pos[1000]; // F - Failure function
int M, N;
void buildFunction()
{
F[0] = -1; int j = -1;
for (int i = 0; i < M; i++)
{
while (j >= 0 && A[i] != A[j])
j = F[j];
j++;
F[i] = j;
}
}
int KMPmatch(int start)
{
int i, j;
for (i = start, j = 0; i < N && j < M; i++, j++)
{
while (j >= 0 && B[i] != A[j])
j = F[j];
}
if (j == M) return i - M + 1;
else return i;
}
int main()
{
in.getline(A, maxn);
in.getline(B, maxn);
N = strlen(B);
M = strlen(A);
buildFunction();
int poz = 0, k = 0;
while (true)
{
poz = KMPmatch(poz);
if (poz > 0 && poz < N) pos[k++] = poz;
else break;
}
out << k << '\n';
int max = (k > 1000 ? 1000 : k);
for (int i = 0; i < max; i++) out << pos[i] << ' ';
return 0;
}