Cod sursa(job #2207098)

Utilizator DordeDorde Matei Dorde Data 24 mai 2018 21:53:34
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
/// Rabin - Karp
#include <fstream>
#include <cstring>
#include <ctype.h>
#include <vector>
#define ll int
using namespace std;
//typedef long long ll;
int const NM = 2000007 , mod = 100007 , mod2 = 100021;
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 = (val + (code (pat [i]) * pw) % mod) % mod;
        val1 = (val1 + (code (pat [i]) * pw2) % mod2) % mod2;
        pw = pw * 62 % mod;
        pw2 = pw2 * 62 % mod2;

    }
    int p1 , p2 ;
    int m = strlen (v + 1);
    pw = pw2 = 1;
    ll z;
    for(i = n ; i >= 1 ; -- i)
    {
        val2 = (val2 + code (v [i]) * pw) % mod;
        val22 = (val22 + code (v [i]) * pw2) % mod2;
        z = pw;
        z2 = pw2;
        pw = pw * 62 % mod;
        pw2 = pw2 * 62 % mod2;
    }
    if(val == val2 && val1 == val22)
    {
        ++ best;
        sol . push_back (0);
    }
    for(p1 = 1 , p2 = n + 1 ; p2 <= m ; ++ p1 , ++ p2)
    {
        val2 = (((val2 + mod) - z * code (v [p1])) % mod * 62 % mod + code (v [p2])) % mod;
        val22 = (((val22 + mod2) - z2 * code (v [p1])) % mod2 * 62 % mod2 + 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;
}