Cod sursa(job #1967619)

Utilizator TimoteiCopaciu Timotei Timotei Data 16 aprilie 2017 21:07:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#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;
}