Cod sursa(job #3203848)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 14 februarie 2024 20:51:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 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(auto i:ans) fout<<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;
            }
            else if(poz==0)
            {
                pii[i]=(s[i]==s[1]);
                break;
            }
            else poz=pii[poz];
        }
        if(pii[i]==lg && ans.size()<1000) ans.push_back(i-2*lg-1);
    }
}