Cod sursa(job #2403845)

Utilizator Chirac_MateiChiriac Matei Chirac_Matei Data 11 aprilie 2019 22:37:06
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <cstring>
#include <vector>
#define MOD 1000000007

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char gs[2000002],s[2000002];
int n,m,i,j;
long long sum,tgsum;
long long nr;
bool ok;
vector <int> ans;
int main()
{
    fin>>(gs+1);
    fin>>(s+1);
    m=strlen(gs+1);
    n=strlen(s+1);
    if(m>n)
    {
        fout<<0;
        return 0;
    }
    for(i=1;i<=m;i++)
    {
        tgsum+=gs[i];
        tgsum%=MOD;
    }
    for(i=1; i<=n-m+1; i++)
    {
        if(i==1)
            for(j=1; j<=m; j++)
            {
                sum+=s[j];
                sum%=MOD;
            }
        else
        {
            sum+=s[i+m-1];
            sum-=s[i-1];
        }
        if(sum==tgsum)
        {
            ok=true;
            for(j=i;j<=m+i-1;j++)
                if(s[j]!=gs[j-i+1])
                {
                    ok=false;
                    break;
                }
            if(ok==true)
                nr++;
            if(nr<=1000)
                ans.push_back(i);
        }
    }
    fout<<nr<<'\n';
    for(auto par : ans)
        fout<<par-1<<' ';
    return 0;
}