Cod sursa(job #2284314)

Utilizator PandaChanTrusca Daria PandaChan Data 17 noiembrie 2018 10:29:56
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char p[2000005], s[2000005];
int hp, h;
int nr, poz[1000];
int putere(int x, int y)
{
    if(x==0)
        return 1;
    for(int i=1; i<x; i++)
        y=y*y;
    return y;
}
int main()
{
    f.getline(p, 2000005);
    f.getline(s, 2000005);
    int n=strlen(p);
    int m=strlen(s);
    int power=1;
    for(int i=n-1; i>=0; i--)
    {
        hp=hp+p[i]*power;
        power=power*n;
    }
    for(int i=0; i<m; i++)
    {
        if(i==0)
        {
            power=1;
            for(int j=n-1; j>=0; j--)
            {
                h=h+s[j]*power;
                power=power*n;
            }
            power/=n;
        }
        else
        {
            int aux=h;
            h=(aux-s[i-1]*power)*n+s[n+i-1];
        }
        if(h==hp)
        {
            nr++;
            poz[nr]=i;
        }
    }
    g<<nr<<endl;
    if(nr<=1000)
        for(int i=1; i<=nr; i++)
            g<<poz[i]<<' ';
    else
        for(int i=1; i<=1000; i++)
            g<<poz[i]<<' ';
    return 0;
}