Cod sursa(job #2207058)

Utilizator DordeDorde Matei Dorde Data 24 mai 2018 20:02:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
/// Rabin - Karp
#include <fstream>
#include <cstring>
#include <ctype.h>
#include <vector>
using namespace std;
typedef long long ll;
int const NM = 2000007 , mod = 1002191 , mod2 = 666013;
char pat [NM] , v [NM];
vector <int> sol;
char const in [] = "strmatch.in";
char const out [] = "strmatch.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;
    freopen (in , "r" , stdin);
    freopen (out , "w" , stdout);
    scanf ("%s\n%s" , (pat + 1) , (v + 1));
    int n = strlen (pat + 1) ;
    ll val = 0 , pw = 1 , val2 = 0 , val1  = 0 , val22 = 0 , pw2 = 1, z2;
    for(i = n ; i >= 1 ; -- i)
    {
        val = 1LL * (val + (1LL * code (pat [i]) * pw) % mod) % mod;
        val1 = 1LL * (val1 + (1LL * code (pat [i]) * pw2) % mod2) % mod2;
        pw = pw * 62LL % mod;
        pw2 = pw2 * 62LL % mod2;

    }
    int p1 , p2 ;
    int m = strlen (v + 1);
    pw = pw2 = 1;
    ll z;
    for(i = n ; i >= 1 ; -- i)
    {
        val2 = (val2 + 1LL * code (v [i]) * pw) % mod;
        val22 = (val22 + 1LL * code (v [i]) * pw2) % mod2;
        z = pw;
        z2 = pw2;
        pw = (pw * 62LL) % mod;
        pw2 = (pw2 * 62LL) % mod2;
    }
    if(val == val2 && val1 == val22)
    {
        ++ best;
        sol . push_back (0);
    }
    for(p1 = 1 , p2 = n + 1 ; p2 <= m ; ++ p1 , ++ p2)
    {
        val2 = 1LL * (1LL * (1LL * ((1LL * (1LL * ((val2 + mod) - 1LL * (z * code (v [p1]) % mod))) % mod) * 62LL ) % mod + 1LL * code (v [p2]) )) % mod;
        val22 = 1LL * (1LL * (1LL * ((1LL * (1LL * ((val22 + mod2) - 1LL * (z2 * code (v [p1]) % mod2))) % mod2) * 62LL ) % mod2 + 1LL * code (v [p2]) )) % mod2;
        if(val == val2 && val1 == val22)
        {
            ++ best ;
            if(sol . size () < 1000)
                sol . push_back (p1);
        }
    }
    printf ("%d\n" , best);
    int it;
    for(it = 0 ; it < sol . size () ; ++ it)
        printf ("%d " , sol [it]);
    return 0;
}