Pagini recente » Cod sursa (job #512114) | Cod sursa (job #2070154) | Cod sursa (job #1873173) | Cod sursa (job #2191550) | Cod sursa (job #896734)
Cod sursa(job #896734)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int maxn = 2000002;
char A[maxn], B[maxn];
int F[maxn], pos[1000]; // Failure function
int M, N;
void buildFunction()
{
int i = 1;
int j = 0;
while (i < M)
{
if (A[i] == A[j])
{
F[i] = j + 1;
i++;
j++;
}
else if (j > 0) j = F[j - 1];
else i++;
}
}
int KMPmatch(int start)
{
int j = 0;
int i = start;
while (i < N)
{
if (A[j] == B[i]) {
if (j == M - 1) return i - M + 1;
i++;
j++;
} else if (j > 0) j = F[j-1];
else i++;
}
return -1;
}
int main()
{
in.getline(A, maxn);
in.getline(B, maxn);
N = strlen(B);
M = strlen(A);
buildFunction();
int poz = 0, k = 0;
while (k < 1000)
{
poz = KMPmatch(poz);
if (poz > 0) { pos[k++] = poz; poz++; }
else break;
}
out << k << '\n';
for (int i = 0; i < k; i++) out << pos[i] << ' ';
return 0;
}