Pagini recente » Cod sursa (job #2482315) | Cod sursa (job #3240872) | Cod sursa (job #2272818) | Cod sursa (job #1540669) | Cod sursa (job #3224550)
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#define NMAX 2000000
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define P 73
#define MOD1 100007
#define MOD2 100021
char A[NMAX+5], B[NMAX+5];
int la, lb;
int pr[NMAX+5];
vector<int> ans;
int main() {
A[0] = B[0] = '#';
fin >> A >> B;
la = strlen(A)-1;
lb = strlen(B)-1;
if (la > lb) {
fout << "0\n";
return 0;
}
int k = 0;
for (int i = 1; i<=la; i++) {
while (k != 0 && A[k] != A[i]) {
k = pr[k-1];
}
if (A[k] == A[i]) k++;
pr[i] = k;
}
k = 0;
for (int i = 0; i<=lb; i++) {
while (k != 0 && A[k] != B[i]) {
k = pr[k-1];
}
if (A[k] == B[i]) k++;
if (k > la) {
ans.push_back(i-la);
}
}
fout << ans.size() << "\n";
for (int i = 0; i<min(1000, (int)ans.size()); i++) {
fout << ans[i] << " ";
}
return 0;
}