Pagini recente » Cod sursa (job #73649) | Cod sursa (job #3270438) | Cod sursa (job #2035449) | Cod sursa (job #2228534) | Cod sursa (job #2634040)
#include <fstream>
#include <iostream>
#include <vector>
#define NMAX 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[NMAX], B[NMAX];
int t[NMAX];
void init() {
t[0] = 0;
int i = 1, j = 0;
while (A[i] != '\0') {
if (A[i] == A[j]) {
t[i] = j + 1;
++i, ++j;
}
else {
if (j == 0)
t[i] = 0, ++i;
else j = t[j - 1];
}
}
}
void KMP() {
int nr = 0;
int i = 0, j = 0;
vector<int> vec;
while (B[j] != '\0') {
if (A[i] == B[j]) {
++i, ++j;
if (A[i] == '\0') { ++nr; if(nr<=1000) vec.push_back(j - i); i = t[i - 1]; }
}
else
if (i == 0)
++j;
else i = t[i - 1];
}
fout << nr << '\n';
for (int x : vec)
fout << x << ' ';
}
int main()
{
fin >> A >> B;
init();
KMP();
return 0;
}