Cod sursa(job #2718536)

Utilizator cyg_SerbanBFlorin Gheorghe cyg_SerbanB Data 8 martie 2021 19:49:09
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
char s1[2000005],s2[2000005];
int pref[2000005];
vector<int> ans;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    int n,m,k;
    scanf("%s\n%s",s1,s2);
    n=strlen(s1);
    m=strlen(s2);
    for(int i=n;i>=1;--i)
        s1[i]=s1[i-1];
    for(int i=m;i>=1;--i)
        s2[i]=s2[i-1];
    k=0;
    pref[1]=0;
    for(int i=2;i<=n;++i)
    {
        while(k>0 && s1[i]!=s1[k+1])
            k=pref[k];
        if(s1[i]==s1[k+1])
            k++;
        pref[i]=k;
    }
    k=0;
    for(int i=1;i<=m;++i)
    {
        while(k>0 && s2[i]!=s1[k+1])
            k=pref[k];
        if(s2[i]==s1[k+1])
            k++;
        if(k==n)
        {
            k=pref[m];
            ans.push_back(i);
        }
    }
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size() && i<1000;++i)
        printf("%d ",ans[i]-1);
    return 0;
}