Pagini recente » Cod sursa (job #2395958) | Cod sursa (job #2947356) | Cod sursa (job #2781912) | Cod sursa (job #458390) | Cod sursa (job #899655)
Cod sursa(job #899655)
#include <fstream>
#include <cstring>
using namespace std;
// Knuth-Morris-Pratt
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int maxn = 2000100;
char A[maxn], B[maxn];
int F[maxn], pos[1010]; // F - Failure function
int M, N, k;
void buildFunction()
{
F[1] = 0; int q;
for (int i = 2; i <= N; i++)
{
q = F[i-1];
while (q > 0 && A[q+1] != A[i])
q = F[q];
if (A[q+1] == A[i]) q++;
F[i] = q;
}
}
void KMPmatch()
{
int q = 0;
for (int i = 1; i <= M; i++)
{
while (q > 0 && A[q+1] != B[i])
q = F[q];
if (B[i] == A[q+1]) q++;
if (q == N)
{
k++;
if (k <= 1000)
pos[k] = i - N;
}
}
}
int main()
{
in.getline(A+1, maxn);
in.getline(B+1, maxn);
N = strlen(A+1);
M = strlen(B+1);
buildFunction();
KMPmatch();
out << k << '\n';
int max = (k <= 1000 ? k : 1000);
for (int i = 1; i <= max; i++) out << pos[i] << ' ';
return 0;
}