Cod sursa(job #2299809)

Utilizator avramraresAvram Rares Stefan avramrares Data 10 decembrie 2018 10:12:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#define Nmax 2*2000000+100
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char pat[Nmax], str[Nmax];
int  phi[Nmax], m, sol;
vector <int> Sol;
inline void build_phi(char pat[] , int x)
{
    int rez=0;
    phi[0]=0;
    for(int i = 1 ; i <= x ; i++ )
    {
        while(rez !=0 && pat[i] != pat[rez])
        {
            rez = phi[rez-1];
        }
        if(pat[i] == pat[rez])
        {
            rez++;
        }
        phi[i] = rez;
    }
}
inline void solve()
{
    strcat(pat, "#");
    strcat(pat, str);
    int x = strlen(pat);
    build_phi( pat , x );
    for(int i = 0 ; i < x ; i ++ )
    {
        if(phi[i] == m && i>=m)
        {
            sol++;
            Sol.push_back(i);
        }
    }
    g<<sol<<'\n';
    for(int i = 0 ; i < Sol.size() ; i++)
    {
        g<<Sol[i] - 2*m << " ";
    }
}
int main()
{
    f.getline(pat , 2000000);
    f.getline(str , 2000000);
    m = strlen(pat);
    solve();
    return 0;
}