Cod sursa(job #3224550)

Utilizator ililogIlinca ililog Data 15 aprilie 2024 16:59:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>

#define NMAX 2000000

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

#define P 73
#define MOD1 100007
#define MOD2 100021

char A[NMAX+5], B[NMAX+5];
int la, lb;

int pr[NMAX+5];
vector<int> ans;

int main() {
    
    A[0] = B[0] = '#';
    fin >> A >> B;
    la = strlen(A)-1;
    lb = strlen(B)-1;
    
    if (la > lb) {
        fout << "0\n";
        return 0;
    }
    int k = 0;
    for (int i = 1; i<=la; i++) {
        while (k != 0 && A[k] != A[i]) {
            k = pr[k-1];
        }
        if (A[k] == A[i]) k++;
        pr[i] = k;
    }
    
    k = 0;
    for (int i = 0; i<=lb; i++) {
        while (k != 0 && A[k] != B[i]) {
            k = pr[k-1];
        }
        if (A[k] == B[i]) k++;
        if (k > la) {
            ans.push_back(i-la);
        }
    }
    
    fout << ans.size() << "\n";
    for (int i = 0; i<min(1000, (int)ans.size()); i++) {
        fout << ans[i] << " ";
    }
    
    return 0;
}