Cod sursa(job #2471464)

Utilizator TudorChirila11Tudor Chirila TudorChirila11 Data 10 octombrie 2019 23:28:44
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
int n, m, i, j, x, k, p[2000005], nr, h[2000005];
int main()
{
    fin>>s1>>s2;
    n=s1.size();
    m=s2.size();
    p[1]=0;
    for(i=1;i<n;i++)
    {
        k=(i+1)/2;
        k--;
        int ok=0;
        while(k>=0)
        {
            if(s1[k+1]==s2[i])
                {p[i]=k+1,ok=1;break;}
            else
            k=p[k];
        }
        if(!ok)
            p[i]=0;
        ///verific pt s[i]
        ///pt i=0;
    }
    for(i=n;i<m;i++)
    {
        k=(i+1)/2-1;
        int ok=0;
        while(k>=0)
        {
            if(s1[k+1]==s2[i])
                {p[i]=k+1,ok=1;break;}
            else
            k=p[k];
        }
        if(!ok)
            p[i]=0;
        if(p[i]==n)
        {
            k=(i+1)/2-1;
            nr++;
            h[nr]=i;
            p[i]=p[k];
        }
    }
    fout<<nr<<'\n';
    for(i=1;i<=nr;i++)
        fout<<h[i]-n+1<<' ';
    fout<<'\n';
    return 0;
}