Cod sursa(job #1670134)

Utilizator alexburdescuBurdescu Alexandru alexburdescu Data 31 martie 2016 14:43:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream  fin("strmatch.in");
ofstream fout("strmatch.out");
int a,i,S,c[1002],j,n,x,k,b,r,Z,t,q;
char A[2000001],B[2000001];
int main ()
{
    fin.get(A,2000001);
    fin.get();
    a=strlen(A);
    S=0;
    Z=0;
    for(i=0;i<=a-1;i++)
    {
        k=int(A[i])*int(A[i]);
        S=(S+k)%100007;
        Z=(Z+k)%100021;
    }
    fin.get(B,2000001);
    b=strlen(B);
    x=1;
        r=0;
        t=0;
        for(j=0;j<=a-1;j++)
        {
            k=int(B[j])*int(B[j]);
            r=(r+k)%100007;
            t=(t+k)%100021;
        }
        if(r==S && t==Z)
        {
            n++;
            if(n<=1000)
            {
                c[x]=i;
                x++;
            }
        }
    for(i=1;i<=b-a;i++)
    {
        q=int(B[i-1])*int(B[i-1]);
        k=int(B[i+a])*int(B[i+a]);
        r=(r+k%100007-q%100007)%100007;
        t=(t+k%100021-q%100021)%100021;
        if(r==S && t==Z)
        {
            n++;
            if(n<=1000)
            {
                c[x]=i;
                x++;
            }
            i++;
        }
    }
    fout<<n<<endl;
    for(i=1;i<=x-1;i++)
    {
        fout<<c[i]<<" ";
    }
    fin.close();
    fout.close();
    return 0;
}