Cod sursa(job #3161067)

Utilizator ililogIlinca ililog Data 25 octombrie 2023 18:48:11
Problema Potrivirea sirurilor Scor 52
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>

#define NMAX 2000000

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char A[NMAX+5], B[NMAX+5];
int la, lb;
int lps[NMAX+5];
int nr;
int pos[1001];

int main() {
    A[0] = B[0] = ' ';
    fin.getline(A+1, NMAX+5);
    fin.getline(B+1, NMAX+5);
    la = strlen(A)-1;
    lb = strlen(B)-1;
    
    lps[1] = 0;
    int j = 0;
   // cout << lps[1] << " "; 
    for (int i = 2; i<=la; i++) {
        while (j && A[j+1] != A[i]) {
            j = lps[j];
        }
        if (A[j+1] == A[i]) {
            j++;
        }
        lps[i] = j;
        //cout << lps[i] << " ";
    }
    
    for (int i = 1; i<=lb; i++) {
        while (j && A[j+1] != B[i]) {
            j = lps[j];
        }
        
        if (A[j+1] == B[i]) {
            j++;
        }
        if (j == la) {
            nr++;
            if (nr <= 1000) {
                pos[nr] = i-la;
            }
            j = lps[la];
        }
    }
    
    fout << nr << "\n";
    for (int i = 1; i<=min(nr, 1000); i++) {
        fout << pos[i] << " ";
    }
    
    return 0;
}