Cod sursa(job #2999068)

Utilizator DordeDorde Matei Dorde Data 10 martie 2023 14:11:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int const N = 2e6 + 3;
int n , m;
char pat[N] , str[N];
int lps[N] , idx[N];
int main()
{
    fin >> pat >> str;
    n = strlen(str);
    m = strlen(pat);
    lps[0] = 0;
    int j = 1 , i = 0;
    while(j < m){
        if(pat[i] == pat[j]){
            lps[j++] = ++i;
        }else{
            if(!i){
                lps[j++] = 0;
            }
            else{
                while(i > 0 && pat[j] != pat[i])
                    i = lps[i - 1];
            }
        }
    }
    int ap = 0;
    i = 0 , j = 0;
    while(i < n){
        if(str[i] == pat[j]){
            ++i , ++j;
            if(j == m){
                idx[ap++] = i - m;
                j = lps[j - 1];
            }
        }else{
            if(j == 0){
                ++i;
            }else{
                j = lps[j - 1];
            }
        }
    }
    fout << ap << '\n';
    for(int i = 0 ; i < min(1000 , ap) ; ++ i)
        fout << idx[i] << ' ';
    fout << '\n';
    return 0;
}