Cod sursa(job #2258881)

Utilizator NewGloryMihnea Andreescu NewGlory Data 12 octombrie 2018 12:54:08
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;

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

inline int f(char ch)
{
    if('a'<=ch && ch<='z')
        return ch-'a';
    return ch-'A'+'z'-'a'+1;
}

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

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

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;
}

string caut,a;
int m,n;
int inv[N];
int sr[N];

inline int get(int st,int dr)
{
    if(st==0)
        return sr[dr];
    int dif=add(sr[dr],-sr[st-1]);
    return mul(dif,inv[st]);
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","r",stdin);
    cin>>caut>>a;
    m=caut.size();
    n=a.size();
    int p=expow(52,N-1);
    inv[N-1]=expow(p,MOD-2);
    for(int i=N-2;i>=0;i--)
        inv[i]=mul(inv[i+1],52);
    int need=0;
    for(int i=0;i<m;i++)
    {
        need=add(need,mul(expow(52,i),f(caut[i])));
    }
    int val=0;
    for(int i=0;i<n;i++)
    {
        val=add(val,mul(expow(52,i),f(a[i])));
        sr[i]=val;
    }
    int ans=0;
    vector<int>a;
    for(int i=0;i+m-1<n;i++)
        if(get(i,i+m-1)==need)
        {
            ans++;
            if(a.size()<1000)
                a.push_back(i);
        }
    cout<<ans<<"\n";
    for(auto x:a)
        cout<<x<<" ";
    cout<<"\n";
    return 0;
}