Cod sursa(job #2953985)

Utilizator RaresPoinaruPoinaru-Rares-Aurel RaresPoinaru Data 12 decembrie 2022 21:15:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int MAXN=4000001;

int dp[MAXN],check,ok;
string s,s1;
vector <int> rez;

int main()
{
    fin >>s>>s1;
    check=s.size ();
    s.push_back ('#');
    s+=s1;
    dp[0]=0;
    for (int i=1;i<s.size ();++i){
        int j=dp[i-1];
        while (j>0 and s[j]!=s[i])
            j=dp[j-1];
        /*if (i==s.size ()-1){
            fout <<dp[1]<<'\n';
        }*/
        dp[i]=j+1;
        if (s[i]!=s[j]) dp[i]=0;
        if (dp[i]==check){
            ok++;
            if (ok<=1000)
                rez.push_back (i-2*check);
        }
    }
    //for (int i=0;i<s.size ();++i){
    //    fout <<dp[i]<<' ';
    //}
    //fout <<'\n'<<'\n';
    fout <<ok<<'\n';
    for (int i=0;i<rez.size ();++i){
        fout <<rez[i]<<' ';
    }
    fin.close ();
    fout.close ();
    return 0;
}