Pagini recente » Cod sursa (job #778257) | Cod sursa (job #2468763) | Cod sursa (job #2746457) | Cod sursa (job #1880622) | Cod sursa (job #3161066)
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#define NMAX 2000000
ifstream fin("strmatch2.in");
ofstream fout("strmatch2.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;
}