Cod sursa(job #2084095)

Utilizator AlexTheDagonBogdan Tudor AlexTheDagon Data 8 decembrie 2017 17:28:03
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
int nr,act,p[2000005],n,m;
vector<int> sol;
int main()
{
    in>>a>>b;
    n=a.size();
    m=b.size();
    if(n>m)
    {
        out<<0;
        return 0;
    }
    p[0]=1;
    act=0;
    nr=0;
    for(int i=1;i<=n+2;++i)p[i]=p[i-1]*97;
    for(int i=0;i<n;++i)nr=nr+(a[i]-'A'+1)*p[i];
    for(int i=0;i<n;++i)act=act+(b[i]-'A'+1)*p[i];
    if(act==nr)sol.pb(0);
    for(int i=n;i<m;++i)
    {
        act=(act-(b[i-n]-'A'+1))/97+(b[i]-'A'+1)*p[n-1];
        if(act==nr)sol.pb(i-n);
    }
    out<<sol.size()<<'\n';
    while(sol.size()>1000)sol.pop_back();
    for(auto i:sol)out<<i+1<<" ";
    return 0;
}