Pagini recente » Cod sursa (job #2984636) | Cod sursa (job #1810684) | Cod sursa (job #3169482) | Cod sursa (job #2338333) | Cod sursa (job #934620)
Cod sursa(job #934620)
#include <fstream>
#include <vector>
#include <string>
#define MAX 2000005
using namespace std;
int N, M, cnt, prefix[MAX];
string A, B;
vector<int> ans;
void citire() {
ifstream in("strmatch.in");
in>>A>>B; in.close();
N = A.length(), M = B.length();
A = " " + A; B = " " + B;
}
void preprocess() {
prefix[1] = 0;
for(int i = 2, P = 0; i <= N; i++) {
while(P && A[P + 1] != A[i]) P = prefix[P];
if(A[P + 1] == A[i]) P++;
prefix[i] = P;
}
}
void solve() {
preprocess();
for(int i = 1, P = 0; i <= M; i++) {
while(P && B[i] != A[P + 1]) P = prefix[P];
if(B[i] == A[P + 1]) P++;
if(P == N) {
cnt++;
if(ans.size() < 1000) ans.push_back(i - N);
P = prefix[P];
}
}
}
void afisare() {
ofstream out("strmatch.out");
out<<cnt<<"\n";
for(size_t i = 0; i < ans.size(); i++) out<<ans[i]<<" ";
out.close();
}
int main() {
citire();
solve();
afisare();
return 0;
}