Cod sursa(job #1713525)

Utilizator cubaLuceafarul cuba Data 5 iunie 2016 20:01:50
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMAX=2000003;
const int Base=73;
char a[NMAX];
char b[NMAX];
int len,lenb;
unsigned long long cifre[NMAX];
unsigned long long Put[20];
vector <int> Poz;
inline unsigned long long Decode(const int st,const int dr)
{
    unsigned long long ret=cifre[dr]-cifre[st-1]*Put[dr-st+1];
    return ret;
}
int main()
{
    unsigned long long sira=0;
    int cnt=0;
    Put[0]=1;
    f>>(a+1);
    f>>(b+1);
    len=strlen(a+1);
    lenb=strlen(b+1);
    for(int i=1;i<=len;i++)
        sira=sira*Base+a[i];
    for(int i=1;i<=lenb;i++)
    {
        Put[i]=Put[i-1]*Base;
        cifre[i]=cifre[i-1]*Base+b[i];
    }
    for(int i=1;i<=lenb;i++)
    {
        if(Decode(i-len+1,i)==sira)
        {
            cnt++;
            if(i<=1000)
                Poz.push_back(i-len);
        }

    }
    g<<cnt<<"\n";
    for(int i=0;i<Poz.size();i++)
        g<<Poz[i]<<" ";
    return 0;
}