Cod sursa(job #912636)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 12 martie 2013 17:21:04
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <cctype>
#include <cstring>
#define DM 2000005
#define MOD 666013
using namespace std;
 
char s1 [DM], s2 [DM];
int answ [1005];
int hash [DM];
 
int nb (char c)
{
    if (tolower (c) == c)
    {
        return (c -'a') + 26;
    }
    else
    {
        return c - 'A';
    }
}
 
long long pw (long long a, long long b)
{
    long long i, rez = 1;
    for (i = 1; i <= b; ++ i)
    {
        rez *= a;
        rez %= MOD;
    }
    return rez;
}
 
long long modineg (long long nb)
{
    nb = nb % MOD;
    if (nb < 0)
    {
        nb += MOD;
    }
    return nb;
}
 
int main()
{
    ifstream f ("strmatch.in");
    ofstream g ("strmatch.out");
 
    long long j, hash1 = 0, n1, n2, i, base = 52, nrc = 0, bpn1m1, ans = 0; //bpn1m1 - base la puterea n1 minus 1
    bool OK;
 
    f >> s1 >> s2;
    n1 = strlen (s1);
    n2 = strlen (s2);
 
    for (i = 0; i < n1; ++ i)
    {
        nrc = nrc + (( pw (base, (n1 - i - 1))) * nb (s2 [i]) % MOD) % MOD;
        hash1 = hash1 + (( pw (base, (n1 - i - 1))) * nb (s1 [i]) % MOD) % MOD;
    }
    hash [0] = nrc;
    bpn1m1 = pw (base, n1 - 1);
 
    for (; i < n2; ++ i)
    {
        nrc = ( (modineg(nrc - ((bpn1m1 * nb (s2 [i - n1])) % MOD)) * base) % MOD + nb (s2 [i])) % MOD;
        hash [i - n1 + 1] = nrc;
    }
    for (i = 0; i < n2 - n1; ++ i)
    {
        if (hash [i] == hash1)
        {
            OK = 1;
            for (j = 0; j < n1 && OK; ++ j)
            {
                if (s1 [j] != s2 [i + j]) OK = 0;
 
            }
            if (OK)
            {
                if (ans < 1000)
                {
                    answ [ans] = i;
                }
                ans ++;
            }
        }
    }
 
    g << ans << "\n";
    for (i = 0; i < ans; ++ i)
        g << answ [i] << " ";
    g << "\n";
    return 0;
}