Cod sursa(job #2554473)

Utilizator AndreiCroitoruAndrei Croitoru AndreiCroitoru Data 22 februarie 2020 22:44:36
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char ch1[2000001];
char ch2[2000001];
char s[4000002];
int pi[4000002];
int ans[10001];
int main()
{
    in.get(ch1+1,2000001);
    int l1=strlen(ch1+1);
    in.get();
    in.get(ch2+1,2000001);
    int l2=strlen(ch2+1);
    int n=l1+l2;
    int i;
    for(i=1;i<=n+1;i++)
    {
        if(i<=l1)
        s[i]=ch1[i];
        else if(i==l1+1)
        s[i]='#';
        else
        s[i]=ch2[i-l1-1];
    }
    pi[1]=0;
    for(i=2;i<=n+1;i++)
    {
        int now=pi[i-1];
        while(now>0 && s[now+1]!=s[i])
        {
            now=pi[now];
        }
        if(s[now+1]==s[i])
        {
            now++;
        }
        pi[i]=now;
    }
    int cnt=0,maxim=0;
    for(i=1;i<=n+1;i++)
    {
        if(pi[i]>maxim)
        maxim=pi[i],cnt=0;
        if(pi[i]==maxim)
        {
            if(cnt<=1000)
            ans[++cnt]=i-l1-1;
        }
    }
    out<<cnt<<'\n';
    for(i=1;i<=cnt;i++)
    {
        out<<ans[i]-l1<<" ";
    }
    return 0;
}