Cod sursa(job #3125464)

Utilizator Turcanu_DavidTurcanu David Turcanu_David Data 3 mai 2023 13:29:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

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

int lps[2000005];

int main()
{
    string a, b;
    fin>>a>>b;
    int prevLPS=0;
    for(int i=1; i<a.size();)
    {
        if(a[i] == a[prevLPS])
        {
            lps[i]=++prevLPS;
            i++;
        }
        else if(prevLPS > 0)
        {
            prevLPS=lps[prevLPS-1];
        }
        else
        {
            lps[i]=0;
            i++;
        }
    }
    int i=0; // b
    int j=0; // a
    vector<int> ans;
    while(i < b.size())
    {
        if(b[i] == a[j])
        {
            i++;
            j++;
        }
        else
        {
            if(j == 0)
            {
                i++;
            }
            else
            {
                j=lps[j-1];
            }
        }
        if(j == a.size())
        {
            ans.push_back(i-a.size());
        }
    }
    fout<<ans.size()<<'\n';
    for(int i=0; i<min(1000, (int)ans.size()); i++)
        fout<<ans[i]<<" ";
    return 0;
}