Cod sursa(job #3030355)

Utilizator raileanu-alin-gabrielRaileanu Alin-Gabriel raileanu-alin-gabriel Data 17 martie 2023 17:10:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>
#include <cstring>
const int NMAX=2000005;

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

char s[NMAX], t[NMAX];
int n, m, pi[NMAX], d[NMAX];

vector <int> ans;

void pii(char []);

int main()
{
    int i, k=-1;
    fin>>s>>t;
    n=strlen(s);
    m=strlen(t);
    pii(s);
    for(i=0; i<m; i++)
    {
        while(k>0 && t[i]!=s[k+1]) k=pi[k];
        if(t[i]==s[k+1]) k++;
        d[i]=k;
        if(k==n-1) ans.push_back(i-n+1);
    }
    fout<<ans.size()<<'\n';
    for(auto i:ans) fout<<i<<' ';
    return 0;
}

void pii(char s[])
{
    int k=-1, i;
    pi[0]=0;
    for(i=1; i<n; i++)
    {
        while(k>0 && s[i]!=s[k+1]) k=pi[k];
        if(s[i]==s[k+1]) k++;
        pi[i]=k;
    }
}