Cod sursa(job #1831520)

Utilizator MithrilBratu Andrei Mithril Data 18 decembrie 2016 11:32:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern,omega;
char x;
int hashOmega[2000005];
int i;
vector<int> aparitii;

int hashString(string &wow, int start, int stop)
{
    const int PRIME = 3079;
    int ans=1;
    for(int j=start;j<=stop;j+=1)
        ans=(ans*(int)wow[j])%PRIME;
    return (int)ans;
}

int main()
{
    fin>>pattern;
    while(fin>>x)
    {
        omega+=x;
        if(omega.size()<pattern.size()) continue;
        hashOmega[i++]=hashString(omega, omega.size()-pattern.size(), omega.size()-1);
    }
    if(pattern.size()>omega.size())
    {
        fout<<0;
        return 0;
    }
    int hashPattern = hashString(pattern, 0, pattern.size()-1);
    for(int j=0;j<i;j+=1)
    {
        if(hashPattern==hashOmega[j])
        {
            bool ok=1;
            for(int y=j,t=0;y<j+pattern.size()&&ok;y+=1,t+=1) if(pattern[t]!=omega[y])ok=0;
            if(ok) aparitii.push_back(j);
        }
    }
    fout<<aparitii.size()<<'\n';
    for(auto j:aparitii) fout<<j<<' ';
    return 0;
}