Cod sursa(job #2044900)

Utilizator HumikoPostu Alexandru Humiko Data 21 octombrie 2017 16:14:53
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

vector <int> rez;
int putere[2000002], baza = 71;
long long h_pat, h_txt[2000002];
char pattern[2000002], text[2000002];
int cnt;

void rabin_karp()
{
    long long modulo = 1000000007;
    int n = strlen(pattern), m = strlen(text);
    for ( int i = n-1; i >= 0; --i )
        h_pat = (h_pat * baza + pattern[i]) % modulo;
    for ( int i = m-1; i >= 0; --i )
        h_txt[i] = (h_txt[i+1] * baza + text[i]) % modulo;
    putere[0] = 1;
    for ( int i = 1; i <= m; ++i )
        putere[i] = (putere[i-1] * baza) % modulo;
    for ( int i = n-1; i < m; ++i )
    {
        long long h_text = h_txt[i-n+1] - (h_txt[i+1]*putere[n]) % modulo;
        if ( h_text < 0 )
            h_text += modulo;
        if ( h_pat == h_text )
        {
            cnt++;
            if ( cnt <= 1000 )
                rez.push_back(i-n+1);
        }
    }
}


int main()
{
    fin>>pattern;
    fin>>text;
    rabin_karp();
    fout<<cnt<<'\n';
    for ( auto x:rez )
        fout<<x<<" ";
}