Pagini recente » Borderou de evaluare (job #829649) | Borderou de evaluare (job #1265431) | Cod sursa (job #1536822)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define MAXN 2000000
using namespace std;
string A, B;
vector <int> sol;
int pi[MAXN + 1];
int n, m;
void make_pi() {
int q = 0;
pi[1] = 0;
for (int i = 2 ; i <= n ; ++i) {
while (q && A[q + 1] != A[i])
q = pi[q];
if (A[q + 1] == A[i])
++q;
pi[i] = q;
}
}
int main () {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> A >> B;
A += 'w';
B += 'w';
n = A.size();
m = B.size();
for (int i = n - 1 ; i > 0 ; --i)
A[i] = A[i - 1];
for (int i = m - 1 ; i > 0 ; --i)
B[i] = B[i - 1];
--n;
--m;
make_pi();
int q = 0;
for (int i = 1 ; i <= m ; ++i) {
while (q && A[q + 1] != B[i])
q = pi[q];
if (A[q + 1] == B[i])
++q;
if (q == n) {
q = pi[n];
if (sol.size() < 1000)
sol.push_back(i);
}
}
cout << sol.size() << "\n";
for (int i = 0 ; i < sol.size() ; ++i)
cout << sol[i] - n << " ";
cout << "\n";
return 0;
}