Cod sursa(job #2344634)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 15 februarie 2019 12:59:15
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int NMAX = 2000005;
const int MOD = 777013;

int n,m;
char A[NMAX];
char B[NMAX];
int rasp[NMAX];

bool verif(int poz)
{
    int ind=n;
    for(int i=poz;i>=poz-n+1;i--)
    {
        if(B[i]!=A[ind]) return 0;
        ind--;
    }
    return 1;
}

int main()
{
    fin >> (A+1);
    fin >> (B+1);
    n=strlen(A+1);
    m=strlen(B+1);
    int put=1,baza=79,nr1=0,nr2=0,putere;
    for(int i=n;i>=1;i--)
    {
        if(i==1) putere=put;
        nr1+=((A[i]-53)*put)%MOD;
        nr1%=MOD;
        put*=baza;
        put%=MOD;
    }
    put=1,nr2=0;
    for(int i=n;i>=1;i--)
    {
        nr2+=((B[i]-53)*put)%MOD;
        nr2%=MOD;
        put*=baza;
        put%=MOD;
    }
    int k=0;
    if(nr1==nr2)
    {
      if(verif(n)==1)
      {
          rasp[++k]=1;
      }
    }
    for(int i=n+1;i<=m;i++)
    {
        nr2-=((B[i-n]-53)*putere)%MOD;
        if(nr2<MOD) nr2+=MOD;
        nr2*=baza;
        nr2+=(B[i]-53);
        nr2%=MOD;
        if(nr1==nr2)
        {
          if(verif(i)==1)
          {
            rasp[++k]=i-n+1;
          }
        }
    }
    fout << k << '\n';
    if(k>1000) k=1000;
    for(int i=1;i<=k;i++) fout << rasp[i]-1 << ' ';
    return 0;
}