Cod sursa(job #2281846)

Utilizator I_am_not_a_robotMr Domino I_am_not_a_robot Data 12 noiembrie 2018 20:19:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;

using namespace std;

const string FILENAME="strmatch";

#define OpenIN() freopen((FILENAME+".in").c_str(),"r",stdin)
#define OpenOUT() freopen((FILENAME+".out").c_str(),"w",stdout)
#define OpenALL() OpenIN(), OpenOUT()
#define infoarena() OpenALL()

const int MOD=1000000007;
const int N=2000000+5;
const int BAZE=47;

inline int add(int a,int b)
{
    a+=b;
    if(a>=MOD)
    {
        a-=MOD;
    }
    if(a<0)
    {
        a+=MOD;
    }
    return a;
}

inline int mul(int a,int b)
{
    return a*(long long)b%MOD;
}

inline int expow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=mul(ans,a);
        }
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}

int p[N];
int inv[N];
int pre[N];

int ans[1005],cnt=0;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    infoarena();
    p[0]=1;
    for(int i=1;i<N;i++)
    {
        p[i]=mul(p[i-1],BAZE);
    }
    inv[N-1]=expow(p[N-1],MOD-2);
    for(int i=N-2;i>=0;i--)
    {
        inv[i]=mul(inv[i+1],BAZE);
    }
    string pat;
    string s;
    cin>>pat>>s;
    int m=pat.size();
    int n=s.size();
    pat="."+pat, s="."+s;
    int PatMask=0;
    for(int i=1;i<=m;i++)
    {
        PatMask=add(PatMask,mul(p[i-1],pat[i]-'A'));
    }
    for(int i=1;i<=n;i++)
    {
        pre[i]=add(pre[i-1],mul(p[i-1],s[i]-'A'));
    }
    for(int st=1;st+m-1<=n;st++)
    {
        int dr=st+m-1;
        int value=add(pre[dr],-pre[st-1]);
        value=mul(value,inv[st-1]);
        if(value==PatMask)
        {
            cnt++;
            if(cnt<=1000)
            {
                ans[cnt]=st-1;
            }
        }
    }
    cout<<cnt<<"\n";
    cnt=min(cnt,1000);
    for(int i=1;i<=cnt;i++)
    {
        cout<<ans[i]<<" ";
    }
    cout<<"\n";
    return 0;
}