Pagini recente » Cod sursa (job #1461913) | Cod sursa (job #2524163) | Cod sursa (job #1360126) | Cod sursa (job #1814155) | Cod sursa (job #2481820)
#include<fstream>
#include<iostream>
#define MAX 2000001
using namespace std;
FILE* f;
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()
{
pi[0] = 0;
for (int i = 1; i < n; ++i)
{
k = pi[i - 1];
while (k > 0 && N[k] != N[i])
k = pi[k - 1];
if (N[i] == N[k])
k++;
pi[i] = k;
}
}
void KMP()
{
int q = 0;
for (int i = 0; i < m; ++i)
{
while (q > 0 && N[q + 1] != M[i])
q = pi[q - 1];
if (N[q+1] == M[i])
q = q + 1;
if (q == n - 1)
{
a[c++] = i - n + 1;
}
cout << q << ' ';
}
}
void readData()
{
char c = 0;
f = fopen("strmatch.in", "r");
n = 0;
m = 0;
while (c != '\n')
{
c = getc(f);
if (c == ' ' || c == '\n')
continue;
N[n] = c;
n++;
}
c = 1;
while (c != EOF)
{
c = getc(f);
if (c == ' ' || c == '\n')
continue;
M[m] = c;
m++;
}
}
int main()
{
readData();
prefixCalculation();
KMP();
g << c << '\n';
for (int i = 0; i < c; ++i)
{
g << a[i] << ' ';
}
}