Cod sursa(job #2684852)

Utilizator Victor24Vasiesiu Victor Victor24 Data 15 decembrie 2020 00:15:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out" );

vector <int> searchh ( string pat, string s )
{
    int mod = 1000000007, d = 256, h = 1, p = 0, t = 0;

    vector < int > sol;

    int M = pat.size();

    for ( int i = 0 ; i < M - 1 ; i++ )
        h = (h*d) % mod;

    for ( int i = 0 ; i < M ; i++ )
    {
        p = (d * p + pat[i]) % mod;
        t = (d * t + s[i] ) % mod;
    }

    for ( int i = 0 ; i <= s.size() - M; i++ )
    {
        if ( p == t )
        {
            int j = i;
            for ( j = i ; j < i + M ; j++ )
            {
                if ( pat[j-i] != s[j]  )
                    break;
            }

            if ( j == i + M )
                sol.push_back(i);
        }

        if ( i == s.size() - M )
            break;

        t = (d*( t - s[i]*h ) + s[i+M]) % mod;

        if ( t < 0 )
            t = t + mod;

    }

    return sol;


}

int main ()
{

    string a, b;

    vector <int> sol;

    f >> a >> b;

    sol = searchh ( a, b );

    g << sol.size() << '\n';

    for ( auto it : sol )
        g << it << " ";
}