Cod sursa(job #2791155)

Utilizator Iulia25Hosu Iulia Iulia25 Data 30 octombrie 2021 10:17:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <cstring>
#include <map>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

int p, ind;
const int NMAX=2e6 + 7;
const int mod=1e9 + 7;
char a[NMAX],b[NMAX];
int poz[1003];
map <long long,int> m;
long long x, y, pow;

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

long long getCode(char c){
    if('a'<=c && c<='z')
        return c-'a'+1;
    else if('A'<=c && c<='Z')
        return c-'A'+27;
    return c-'0'+53;
}

int main()  {
    int n,m;
    a[0]='a';
    b[0]='a';
    cin>>(a+1);
    cin>>(b+1);
    n=strlen(a)-1;
    m=strlen(b)-1;
    x=0;
    pow=1;
    for(int i=1;i<=n;i++){
        x=(x*63+getCode(a[i]))%mod;
        y=(y*63+getCode(b[i]))%mod;
        if(i!=1)
            pow*=63;
        pow%=mod;
    }
    for(int i=1;i<=m-n+1;i++){
        if(x==y)    {
            ++p;
            if(ind<1000)
            poz[++ind]=i;
        }
        y-=getCode(b[i])*pow;
        y%=mod;
        if(y<0)
            y+=mod;
        y=y*63+getCode(b[i+n]);
        y%=mod;
    }
    cout<<p<<'\n';
    for(int i=1;i<=ind;i++)
        cout<<poz[i] - 1<<' ';
    cout<<'\n';
    return 0;
}