Cod sursa(job #3257480)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 17 noiembrie 2024 20:47:23
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 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 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+='#';
    s+=t;

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



    return 0;
}