Cod sursa(job #2063492)

Utilizator patricia.predaPatricia Preda patricia.preda Data 11 noiembrie 2017 11:49:08
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define MOD 101
#define Lg 20000005

using namespace std;

int sol[Lg];
char a[Lg],b[Lg];
int n,m,h,put;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(a,Lg,stdin);
    fgets(b,Lg,stdin);
    n=strlen(a)-1;
    m=strlen(b)-1;
    put=1;
    h=a[0]%MOD;
    int loc=b[0]%MOD;
    for(int i=1; i<n; i++)
    {
        h=(h*256+a[i])%MOD;
        put=put*256%MOD;
        loc=(loc*256+b[i])%MOD;
    }
    for(int i=n; i<m; i++)
    {
        if(loc==h)
        {
            int k=i-n;
            for(int j=0; j<n; j++)
            {
                if(a[j]!=b[k])
                    break ;
                k++;
            }
            if(k==i)
                sol[++sol[0]]=i-n;

        }
        loc=(((loc-(b[i-n]*put%101)+101)*256%101)+b[i])%101;
    }
    if(loc==h)
    {
        int k=m-n;
        for(int j=0; j<n; j++)
        {
            if(a[j]!=b[k])
                break ;
            k++;
        }
        if(k==m)
            sol[++sol[0]]=m-n;
    }
    cout<<sol[0]<<"\n";
    int ll=min(sol[0],1000);
    for(int i=1; i<=ll; i++)
        cout<<sol[i]<<" ";
    return 0;
}