Cod sursa(job #2084109)

Utilizator AlexTheDagonBogdan Tudor AlexTheDagon Data 8 decembrie 2017 17:40:12
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 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;
long long nr,act,p[2000005],n,m,sp[2000005];
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<m;++i)
        p[i]=p[i-1]*97;
    sp[0]=a[0]-'A'+1;;
    for(int i=1;i<m;++i)
        sp[i]=sp[i-1]+(b[i]-'A'+1)*p[i];
    for(int i=0;i<n;++i)
        nr=nr+(a[i]-'A'+1)*p[i];
    nr=nr*p[m-n];
    if(nr==sp[n])sol.pb(0);
    for(int i=n;i<m;++i)
        if((sp[i]-sp[i-n])*p[m-1-i]==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;
}