Cod sursa(job #1276134)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 25 noiembrie 2014 23:27:32
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define N 2000002
#define P 191LL
#define mod 6074001001LL


char substr[N],str[N];

int main ()
{
    FILE *fin=fopen("strmatch.in","r");
    FILE *fout=fopen("strmatch.out","w");

    fscanf(fin,"%s %s", substr, str);
    long long int hash_substr = 0LL;
    int len = strlen(substr);
    long long int P_len = 1LL;
    for(int i=0;i<len; i++)
    {
        hash_substr = (hash_substr * P + substr[i]) % mod;
        P_len = (P_len * P) % mod;
    }

    long long int hash_str=0;
    int i;
    for(i=0;i<len;i++)
    {
        hash_str = (hash_str*P + str[i]) % mod;
    }
    std::vector<int> v;
    for(;i<strlen(str);i++)
    {
        if(hash_str==hash_substr)
        {
            int flag = true;
            v.push_back(i-len);
            /*
            for(int j=0;j<len;j++)
            {
                if(substr[j] != str[i+j-len])
                {
                    flag=false;
                }
            }
            if(flag)
            {
            }
            */
        }
        hash_str = (hash_str * P + str[i] - P_len*str[i - len]) % mod;
    }
    fprintf(fout, "%d\n", v.size());
    for(auto& e: v)
    {
        fprintf(fout, "%d ", e);
    }
    return 0;
}