Cod sursa(job #2870903)

Utilizator LuxinMatMatasaru Luxin Gabriel LuxinMat Data 12 martie 2022 17:28:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include<fstream>
#include<cstring>
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

char s1[4000002], s2[2000001];
int pi[2000001], rez[1001];

void kmp()
{
    pi[0] = 0;
    int len = strlen(s1);
    for(int i=1; i<len; i++)
    {
        int j = pi[i-1];
        if(j>0 && s1[j] != s1[i])
            j = pi[j-1];
        if(s1[i] == s1[j])
            j++;
        pi[i] = j;
    }
}

int main()
{
    cin.getline(s1, 2000001);
    cin.getline(s2, 2000001);
    strcat(s1, "#");
    int len1 = strlen(s1);
    strcat(s1, s2);
    int len2 = strlen(s1);
    kmp();
    int ct = 0;
    for(int i=len1; i<len2; i++)
    {
        if(pi[i] == len1-1 && ct<1000)
            rez[++ct] = i-len1-2;
    }
    cout<<ct<<'\n';
    for(int i=1; i<=ct; i++)
        cout<<rez[i]<<" ";
    return 0;
}