Cod sursa(job #2717189)

Utilizator AlexMariMarinescu Alexandru AlexMari Data 6 martie 2021 16:39:41
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char s1[2000005],s2[2000005];


int prefix[2000005],n,m;

vector<int>ans;

int main()
{
    fin>>s1;
    fin>>s2;
    n=strlen(s1);
    m=strlen(s2);
    int j=0;
    for(int i=1;i<=n-1;i++)
    {
        while(j>0&&s1[i]!=s1[j])
            j=prefix[j-1];
        if(s1[i]==s1[j])
            j++;
        prefix[i]=j;
    }
    j=0;
    for(int i=1;i<m;i++)
    {
        while(s2[i]!=s1[j]&&j>0)
            j=prefix[j-1];
        if(s2[i]==s1[j])
           j++;
        if(j==n)
            ans.push_back(i-n+1);
    }
    fout<<ans.size()<<'\n';
    int val=ans.size();
    val=min(val,1000);
    for(int i=0;i<val;i++)
        fout<<ans[i]<<" ";
    return 0;
}