Pagini recente » Cod sursa (job #1703223) | Cod sursa (job #117363) | Cod sursa (job #1495719) | Cod sursa (job #2768511) | Cod sursa (job #1967619)
#include <iostream>
#include <fstream>
#include <vector>
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define FORR(i, x, y) for(int i = x; i >= y; --i)
#define pb(x) push_back(x)
#define sz() size()
#define mod1 100007
#define mod2 100021
#define mMax 2000005
using namespace std;
int pi[mMax], m, n;
vector <int> sol;
string T, P;
void update_pi()
{
int idx = -1;
pi[0] = 0;
FOR(i, 1, m){
while(idx > 0 && P[idx + 1] != P[i]) idx = pi[idx];
if(P[idx + 1] == P[i]) idx++;
pi[i] = idx;
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> P >> T;
m = P.sz() - 1;
n = T.sz() - 1;
if(n < m){
fout << 0;
return 0;
}
update_pi();
int k = -1;
FOR(i, 0, n){
while(k > 0 && P[k + 1] != T[i]) k = pi[k];
if(P[k + 1] == T[i]) k++;
if(k == m){
sol.pb(i - m);
k = pi[k];
}
}
int x = sol.sz();
fout << x << '\n';
FOR(i, 0, min(x - 1, 999))
fout << sol[i] << ' ';
return 0;
}