Pagini recente » Cod sursa (job #2443401) | Cod sursa (job #739243) | Cod sursa (job #1420988) | Cod sursa (job #2970982) | Cod sursa (job #3161067)
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#define NMAX 2000000
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[NMAX+5], B[NMAX+5];
int la, lb;
int lps[NMAX+5];
int nr;
int pos[1001];
int main() {
A[0] = B[0] = ' ';
fin.getline(A+1, NMAX+5);
fin.getline(B+1, NMAX+5);
la = strlen(A)-1;
lb = strlen(B)-1;
lps[1] = 0;
int j = 0;
// cout << lps[1] << " ";
for (int i = 2; i<=la; i++) {
while (j && A[j+1] != A[i]) {
j = lps[j];
}
if (A[j+1] == A[i]) {
j++;
}
lps[i] = j;
//cout << lps[i] << " ";
}
for (int i = 1; i<=lb; i++) {
while (j && A[j+1] != B[i]) {
j = lps[j];
}
if (A[j+1] == B[i]) {
j++;
}
if (j == la) {
nr++;
if (nr <= 1000) {
pos[nr] = i-la;
}
j = lps[la];
}
}
fout << nr << "\n";
for (int i = 1; i<=min(nr, 1000); i++) {
fout << pos[i] << " ";
}
return 0;
}