Cod sursa(job #3004372)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 16 martie 2023 12:01:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 2e6+2;
int n,m;
string pattern,text;
int table[nmax];
int pref_length[nmax];

inline void build_table()
{
    int i=0,j=1;
    while(j<pattern.length())
    {
        if(pattern[i] == pattern[j])
        {
            table[j] = i + 1;
            i++;
            j++;
        }
        else if(i>0)
        {
            i = table[i-1];
        }
        else
        {
            table[j] = 0;
            j++;
        }
    }
}

inline void kmp_search()
{
    int i=0,j=0;
    while(j < text.length()) //j->text; i->pattern
    {
        if(text[j] == pattern[i])
        {
            pref_length[j] = i + 1;
            i++;
            j++;
            if(i == pattern.length())
            {
                i = table[i-1];
            }
        }
        else if(i>0)
        {
            i = table[i - 1];
        }
        else
        {
            pref_length[j] = 0;
            j++;
        }
    }
}

int main()
{
    fin>>pattern>>text;
    build_table();
    kmp_search();
    vector<int> rasp;
    for(int i=0; i<text.length(); i++)
    {
        if(pref_length[i] == pattern.length() && rasp.size() < 1000)
            rasp.push_back(i - pattern.length() + 1);
    }
    fout<<rasp.size()<<"\n";
    for(auto r: rasp) fout<<r<<" ";
    return 0;
}