Cod sursa(job #3262747)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 11 decembrie 2024 14:40:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
const int NMAX = 2000001;
int prefix[NMAX];
void calculatePrefix (const string& pat)
{
    int lg = 0, n = pat.size();
    prefix[0] = 0;
    for (int i = 1; i < n; i++)
    {
        while (pat[i] != pat[lg] && lg != 0)
            lg = prefix[lg - 1];
        if (pat[i] == pat[lg])
            lg++;
        prefix[i] = lg;
    }
}
int getOccurences (string &pat, string& txt, vector<int> &ans)
{
    int cnt = 0, m = txt.size(), n = pat.size();
    int lg = 0;
    for (int i = 0; i < m; i++)
    {
        if (pat[lg] == txt[i])
        {
            lg++;
        }
        else
        {
            while (txt[i] != pat[lg] && lg != 0)
                lg = prefix[lg - 1];
            if (txt[i] == pat[lg])
                lg++;
        }
        if (lg == n)
        {
            cnt ++;
            if (cnt <= 1000)
                ans.push_back (i - lg + 1);
            lg = prefix[lg - 1];
        }
    }
    return cnt;
}
int main()
{
    string txt, pat;
    f >> pat >> txt;
    calculatePrefix (pat);
    vector<int>ans;
    g << getOccurences (pat, txt, ans) << '\n';
    for (auto pos : ans)
    {
        g << pos << ' ';
    }
    return 0;
}