Cod sursa(job #1409495)

Utilizator ArhivaArhiva Infoarena Arhiva Data 30 martie 2015 15:57:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
///Rabin-Karp ALGORITHM
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define ull unsigned long long
using namespace std;
const int NMAX = 2000004;
const int Base = 53;
char a[NMAX], b[NMAX];
int sol[1004], lg, n, m;
ull Pow[NMAX], H[NMAX];
inline void Solve()
{
    ull Codif=0;
    for(int i=1;i<=n;++i)
        Codif = Codif*Base+a[i]-'A';
    Pow[0] = 1;
    for(int i=1;i<=m;++i)
    {
        H[i] = H[i-1]*Base+b[i]-'A';
        Pow[i] = Pow[i-1]*Base;
        if(i >= n)
        {
            ull x = H[i]-Pow[n]*H[i-n];
            if(x==Codif)
            {
                ++lg;
                if(lg<=1000)
                    sol[lg] = i-n;
            }
        }
    }
}
inline void Write()
{
    printf("%d\n",lg);
    lg = min(lg,1000);
    for(int i=1;i<=lg;++i)
        printf("%d ",sol[i]);
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",(a+1),(b+1));
    n = strlen(a+1), m = strlen(b+1);
    Solve();
    Write();
    return 0;
}