Cod sursa(job #3178704)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 2 decembrie 2023 11:29:48
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char pattern[2000001],txt[2000001];
int dp[2000001],rez,n,m;
int poz[1001];
void search(int i, int j)
{
    while(i<m)
    {
        if(txt[i]==pattern[j])
        {
            j++;
            i++;
            if(j==n)
            {
                rez++;
                poz[rez]=i-n;
                if(rez==1000)
                    return;
                j=dp[n-1];
            }
        }
        else
        {
            if(j==0)
                i++;
            else
                j=dp[j];
        }
    }
}
int ps(int k, char c)
{
    if(k==0)
    {
        if(pattern[0]==c)
            return 1;
        else
            return 0;
    }
    else
    if(pattern[k]==c)
        return k+1;
    else
        return ps(dp[k-1],c);
}
int main()
{
    cin>>pattern>>txt;
    n=strlen(pattern);
    m=strlen(txt);
    int i;
    for(i=1;i<n;i++)
    {
        dp[i]=ps(dp[i-1],pattern[i]);
    }
    search(0,0);
    cout<<rez<<'\n';
    for(i=1;i<=rez;i++)
        cout<<poz[i]<<" ";
    return 0;
}