Cod sursa(job #2134186)

Utilizator sebi110Ciobanu Sebastian sebi110 Data 17 februarie 2018 18:27:16
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <string.h>
#define nmax 2000000
#define INF 1000000
#define MOD 1000000007
#define baz 73
using namespace std;

int mypow(int x,int p)
{
    if(p==0)
        return 1;
    if(p==1)
        return x;
    long long rez=mypow(x,p/2);
    if(p%2==0)
        return (rez*rez)%MOD;
    return (rez*rez*x)%MOD;
}
char a[nmax],b[nmax];
int ans[1001];
long long act;
int invmod(int x)
{
    return mypow(x,MOD);
}
int main()
{
    int n,m,i,sear=0,rez=0,p=1;
    cin>>a;
    cin>>b;
    m=strlen(a);
    n=strlen(b);
    sear=a[0];
    for(i=1;i<m;i++)
    {
        sear=(sear*baz+a[i])%MOD;
        p=(p*baz)%MOD;
    }
    for(i=0;i<m;i++)
        act=(act*baz+b[i])%MOD;
    if(act==sear)
    {
        rez++;
        ans[rez]=0;
    }
    for(i=m;i<n;i++)
    {
        act=((act-(b[i-m]*p)%MOD+MOD)*baz+b[i])%MOD;
        if(act==sear)
        {
            rez++;
            ans[rez]=i-m+1;
        }
    }
    cout<<rez<<'\n';
    for(i=1;i<=rez;i++)
        cout<<ans[i]<<' ';
    return 0;
}