Cod sursa(job #3203849)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 14 februarie 2024 21:06:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <cstring>
#include <vector>
const int NMAX=2000005;

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

void pi(char *s);

char s[2*NMAX], t[NMAX];
int pii[2*NMAX], lg, i;
vector <int> ans;

int main()
{
    fin>>s;
    lg=strlen(s);
    for(i=lg; i>=1; i--) s[i]=s[i-1];
    fin>>t;
    strcat(s, "#");
    strcat(s, t);
    pi(s);
    fout<<ans.size()<<'\n';
    for(i=0; i<min(int(ans.size()), 1000); i++) fout<<ans[i]<<' ';
    return 0;
}

void pi(char *s)
{
    int i, poz;
    pii[1]=0;
    for(i=2; s[i]; i++)
    {
        poz=i-1;
        while(true)
        {
            if(s[pii[poz]+1]==s[i])
            {
                pii[i]=pii[poz]+1;
                break;
            }
            if(poz==0) break;
            poz=pii[poz];
        }
        if(s[i]!='#' && pii[i]==lg) ans.push_back(i-2*lg-1);
    }
}