Cod sursa(job #3256103)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 13 noiembrie 2024 14:38:29
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <bits/stdc++.h>
#include <fstream>
#define VMAX 4000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

int lps[VMAX];
string s,t;
vector<int> pozitii_sir_intampinat;

int aflare_lps(int indic,int nr_initial)
{
    if(s[lps[indic-1]]==s[nr_initial])
        return lps[indic-1]+1;
    else
    {
        if(indic<=1)
            return -1;
        return aflare_lps(lps[indic],nr_initial);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n,m,i,j,k,q,nr,suma,maxim,minim,len_s;
    fin>>s>>t;
    len_s=s.size();
    s+=t;

    nr=0;
    for(i=1;i<s.size();i++)
    {
        lps[i]=aflare_lps(i,i);
        if(lps[i]==-1)
        {
            if(s[0]==s[i])
                lps[i]=1;
            else
                lps[i]=0;
        }
        if(lps[i]>=len_s)
        {
            nr++;
            pozitii_sir_intampinat.push_back(i-2*len_s+1);
        }
    }
    fout<<nr<<'\n';
    for(i=0;i<pozitii_sir_intampinat.size();i++)
        fout<<pozitii_sir_intampinat[i]<<' ';
    fout<<'\n';



    return 0;
}