Pagini recente » Cod sursa (job #616016) | Cod sursa (job #2876977) | Cod sursa (job #1219547) | Cod sursa (job #1839860) | Cod sursa (job #1249218)
#include <fstream>
#define Nmax (1 << 10)
#define Smax 2000100
#define root 0
using namespace std;
int N, nS, Fail[Smax], Solution[Nmax];
char A[Smax], B[Smax];
void Kmp() {
int i, node;
node = root;
for(i = 1; B[i]; i++) {
while(node != root && B[i] != A[node + 1])
node = Fail[node];
if(B[i] == A[node + 1])
node++;
if(node == N) {
node = Fail[node];
++nS;
if(nS <= 1000)
Solution[nS] = i - N;
}
}
}
void Prefix() {
int i, node;
node = root;
Fail[1] = root;
for(i = 2; A[i]; i++) {
while(node != root && A[i] != A[node + 1])
node = Fail[node];
if(A[i] == A[node + 1])
node++;
Fail[i] = node;
}
N = i - 1;
}
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 << nS << '\n';
nS = min(nS, 1000);
for(int i = 1; i <= nS; i++)
out << Solution[i] << ' ';
out << '\n';
out.close();
}
int main() {
Read();
Prefix();
Kmp();
Write();
return 0;
}