Cod sursa(job #2207024)

Utilizator DordeDorde Matei Dorde Data 24 mai 2018 19:24:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
/// Rabin - Karp
#include <fstream>
#include <cstring>
#include <ctype.h>
#include <vector>
using namespace std;
typedef long long ll;
ll const NM = 2000007 , mod = 1000003;
char pat [NM] , v [NM];
vector <int> sol;
char const in [] = "strmatch.in";
char const out [] = "strmatch.out";
ifstream cin (in);
ofstream cout (out);
inline int code (char x)
{
    if (isdigit (x))
        return x - '0';
    if(isalpha (x) && x <= 'Z')
        return x - 'A' + 10;
    return x - 'a' + 36;
}
int best;
int main()
{
    int i;
    cin >> pat + 1 >> v + 1;
    cin . close ();
    int n = strlen (pat + 1) ;
    ll val = 0 , pw = 1 , val2 = 0;
    for(i = n ; i >= 1 ; -- i)
    {
        val = 1LL * (val + (1LL * code (pat [i]) * pw) % mod) % mod;
        pw = pw * 62LL % mod;
    }
    int p1 , p2 ;
    int m = strlen (v + 1);
    pw = 1;
    ll z;
    for(i = n ; i >= 1 ; -- i)
    {
        val2 = val2 + 1LL * code (v [i]) * pw;
        val2 %= mod;
        z = pw;
        pw = pw * 62LL;
        pw %= mod;
    }
    for(p1 = 1 , p2 = n ; p2 <= m + 1 ; ++ p1 , ++ p2)
    {
        if(val == val2)
        {
            ++ best ;
            if(sol . size () < 1000)
                sol . push_back (p1 - 1);
        }
        val2 = 1LL * ((val2 + mod) - 1LL * (z * code (v [p1]) % mod));
        val2 = val2 % mod;
        val2 = 62LL * val2;
        val2 %= mod;
        val2 = 1LL * (val2 + code (v [p2 + 1]));
        val2 %= mod;
    }
    cout << best << '\n';
    int it;
    for(it = 0 ; it < sol . size () ; ++ it)
        cout << sol [it] << ' ';
    return 0;
}