Pagini recente » Cod sursa (job #509133) | Cod sursa (job #1686137) | Cod sursa (job #2711937) | Cod sursa (job #648770) | Cod sursa (job #970222)
Cod sursa(job #970222)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int Nmax = 2000009;
int N; int M; char A[Nmax]; char B[Nmax]; int H[Nmax]; int q = 0;
vector <int> V;
void Read() {
fin >> A + 1; fin.get();
fin >> B + 1;
N = strlen(A + 1);
M = strlen(B + 1);
}
void Precalc() {
for(int i = 2; i <= N; ++i) {
while(q > 0 && A[i] != A[q + 1])
q = H[q];
if(A[i] == A[q + 1]) ++q;
H[i] = q;
}
}
void Solve() {
q = 0;
for(int i = 1; i <= M; ++i) {
while(q && B[i] != A[q + 1])
q = H[q];
if(A[q + 1] == B[i]) ++q;
if(q == N) V.push_back(i - q);
}
}
void Print() {
fout << V.size() <<'\n';
for(int i = 0 ; i < V.size(); ++i)
fout << V[i] << " ";
}
int main() {
Read();
Precalc(); Solve (); Print ();
return 0;
}