Cod sursa(job #1867901)

Utilizator r00t_Roman Remus r00t_ Data 4 februarie 2017 13:45:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
//das karp
#include <vector>
#include <algorithm>
#include <cmath>
#include <algorithm>
#include <string>
#include <fstream>
#define ll long long
using namespace std;

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

int prim = 3;
string a,b;

ll geth(int n,int p,ll inh){
    inh -= b[n]-'A'+1;
    inh/=prim;
    inh+= (b[p]-'A'+1)*pow(prim,p-n-1);
    return inh;
}

int mycheck(int aux){
    int rez = aux;
    for(int i=0;i<a.size();i++,aux++){
        if(a[i] != b[aux])
            return -1;
    }
    return rez;
}



int main()
{
    vector<int>rez;
    int ih=0,sh=0;
    fin>>a>>b;

    for(int i=0;i<a.size();i++){
        sh+=(a[i]-'A'+1)*pow(prim,i);
        ih+=(b[i]-'A'+1)*pow(prim,i);
    }
    int aux=0;
    for(int i=a.size()-1;i<b.size();i++){
        if(sh == ih){
            if(mycheck(aux)!=-1){
                rez.push_back(aux);
            }
            aux++;
        }
        else {
            ih = geth(aux,i+1,ih);
            aux++;
        }
    }
    fout<<rez.size()<<'\n';
    for(int i=0;i<rez.size();i++)
        if(i<=999)
            fout<<rez[i]<<' ';
        else
            break;

    return 0;
}