Pagini recente » Cod sursa (job #2980814) | Cod sursa (job #2775749) | Cod sursa (job #2983196) | Cod sursa (job #386711) | Cod sursa (job #2482575)
#include<fstream>
#include<iostream>
#include<string.h>
#define MAX 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int m, n, k, c, pi[MAX];
char N[MAX], M[MAX]; //N - pattern, M - big string
int a[MAX];
//ABA
//CABBCABABAB
//0001123
//k = 0
void prefixCalculation()
{
int j = 0;
for (int i = 1; i < n; ++i)
{
while (j > 0 && N[i] != N[j])
j = pi[j - 1];
if (N[i] == N[j])
j++;
pi[i] = j;
}
}
//AAAAA
//ABA
//010
void KMP()
{
int q = 0;
for (int i = 0; i < m; ++i)
{
while (q > 0 && N[q] != M[i])
q = pi[q - 1];
if (N[q] == M[i])
++q;
if (q == n)
{
a[c++] = i - n + 1;
if (c > 1000)
return;
}
}
}
void readData()
{
f.getline(N, MAX);
f.getline(M, MAX);
n = strlen(N);
m = strlen(M);
}
int main()
{
readData();
prefixCalculation();
KMP();
g << c << '\n';
for (int i = 0; i < c; ++i)
{
g << a[i] << ' ';
}
}