Pagini recente » Cod sursa (job #2032571) | Cod sursa (job #2231146) | Cod sursa (job #1221454) | Cod sursa (job #2143233) | Cod sursa (job #2380970)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMax 2000010
string A, B;
int n, m;
int urm[NMax];
vector<int> poz;
void prefix(string &);
void solve();
int main(){
fin >> A >> B;
m = A.size();
n = B.size();
prefix(A);
solve();
fout << poz.size() << '\n';
for(int i = 0; i < poz.size() && i < 1000; i++) fout << poz[i] << ' ';
}
void prefix(string & A){
int x, k;
urm[0] = -1;
k = -1;
for(x = 1; x < m; x++){
while(k >= 0 && A[k + 1] != A[x]) k = urm[k];
if(A[k + 1] == A[x]) k++;
urm[x] = k;
}
}
void solve(){
int i, x;
x = -1;
for(i = 0; i < n; i++){
while(x >= 0 && A[x + 1] != B[i]) x = urm[x];
if(A[x + 1] == B[i]) x++;
if(x == m - 1){
poz.push_back(i - m + 1);
x = urm[x];
}
}
}