Cod sursa(job #2869978)

Utilizator CristianPavelCristian Pavel CristianPavel Data 11 martie 2022 23:07:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <cstring>
#define maxN 2000001
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

char s1[maxN], s2[maxN];
int Poz[maxN], Nr = 0; 
int Lps[maxN];

void Lps_ (char s1[])
{
    int l1 = strlen(s1);
    int i = 1, j = 0;
    Lps[0] = 0;
    while(i < l1)
    {
        if(s1[i] == s1[j]){
            j++;
            Lps[i] = j;
            i++;
        }
        else{
            if(j == 0){
                Lps[i] = 0;
                i++;
            }
            else j = Lps[j-1];
        }
    }
}

void Kmp (char s1[], char s2[])
{
    int l1 = strlen(s1), l2 = strlen(s2);
    int i = 0, j = 0;
    while(i < l2)
    {
        if(s2[i] == s1[j]) i++, j++;
        if(j == l1){
            Nr++;
            Poz[Nr] = i - j;
            j = Lps[j-1];
        }
        else if(s2[i] != s1[j])
            if(j != 0) j = Lps[j-1];
            else i++;
    }
}

int main()
{
    cin.get(s1, maxN);
    cin.get();
    cin.get(s2 ,maxN);
    Lps_(s1);
    Kmp(s1, s2);
    cout << Nr <<"\n";
    for(int i = 1; i <= Nr && i <= 1000; i++)
    {
        cout << Poz[i] << " ";
    }
    return 0;

}