Cod sursa(job #2999018)

Utilizator DordeDorde Matei Dorde Data 10 martie 2023 13:11:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 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[1001];
int main()
{
    fin >> pat >> str;
    n = strlen(str);
    m = strlen(pat);
    lps[0] = -1;
    int j = 1 , i = 0;
    while(j < m){
        if(pat[i] == pat[j])
            lps[j] = lps[i];
        else{
            lps[j] = i;
            while(i >= 0 && pat[i] != pat[j])
                i = lps[i];
        }
        ++i , ++j;
    }
    lps[j] = i;
    int ap = 0;
    i = 0 , j = 0;
    while(ap < 1000 && i < n){
        if(str[i] == pat[j]){
            ++i , ++j;
            if(j == m){
                idx[++ap] = i - m;
                j = lps[j];
            }
        }else{
            j = lps[j];
            if(j == -1){
                ++i , ++j;
            }
        }
    }
    fout << ap << '\n';
    for(int i = 1 ; i <= ap ; ++ i)
        fout << idx[i] << ' ';
    fout << '\n';
    return 0;
}