Pagini recente » Cod sursa (job #14799) | Cod sursa (job #404913) | Cod sursa (job #288719) | Cod sursa (job #1164698) | Cod sursa (job #2060656)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int cnt;
int S[NMAX];
char A[NMAX], B[NMAX];
vector <int> rsp;
void kmp(char sir[], char key[])
{
int n = strlen(sir + 1);
int m = strlen(key + 1);
S[0] = -1;
S[1] = 0;
for (int i = 2; i <= m; i++)
{
int prv = i - 1;
char ch = key[i];
while (S[prv] != -1 && key[S[prv] + 1] != ch)
prv = S[prv];
S[i] = S[prv] + 1;
}
int lst = 0;
for (int i = 1; i <= n; i++)
{
while (lst != -1)
if (key[lst + 1] == sir[i])
break;
else lst = S[lst];
lst++;
if (lst == m)
{
rsp.push_back(i - m);
lst = S[lst];
}
}
}
void write()
{
fout << rsp.size() << "\n";
vector <int> :: iterator it;
for (it = rsp.begin(); it != rsp.end(); it++)
{
if (++cnt > 1000)
break;
fout << *it << " ";
}
}
int main()
{
fin >> (A + 1) >> (B + 1);
kmp(B, A);
write();
return 0;
}