Pagini recente » Cod sursa (job #2344464) | Cod sursa (job #9485) | Cod sursa (job #530155) | Cod sursa (job #694625) | Cod sursa (job #1332163)
#include <fstream>
#define Nmax (1 << 10)
#define Smax 2000100
#define root 0
using namespace std;
int N, Solutions, Fail[Smax], Solution[Nmax];
char A[Smax], B[Smax];
void Kmp() {
int i, p, top = 0;
p = root;
for(i = 1; B[i]; i++) {
while(p != root && A[p + 1] != B[i])
p = Fail[p];
if(A[p + 1] == B[i])
p++;
if(A[p + 1] == 0) {
++Solutions;
if(top < 1000) {
Solution[++top] = i - p;
}
}
}
}
void Prefix() {
int i, p;
p = root;
Fail[1] = root;
for(i = 2; A[i]; i++) {
while(p != root && A[p + 1] != A[i])
p = Fail[p];
if(A[p + 1] == A[i])
p++;
Fail[i] = p;
}
}
void Read() {
ifstream in("strmatch.in");
in.getline(A + 1, Smax);
in.getline(B + 1, Smax);
in.close();
}
void Write() {
ofstream out("strmatch.out");
out << Solutions << '\n';
Solutions = min(Solutions, 1000);
for(int i = 1; i <= Solutions; i++)
out << Solution[i] << ' ';
out << '\n';
out.close();
}
int main() {
Read();
Prefix();
Kmp();
Write();
return 0;
}