Cod sursa(job #2910788)

Utilizator divadddDavid Curca divaddd Data 25 iunie 2022 00:20:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
#define MAX 2000002
using namespace std;
char A[MAX],B[MAX];
int p[MAX],ans;
vector<int> sol;

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

int main()
{
    fin >> A+1;
    fin >> B+1;
    int a = strlen(A+1);
    int b = strlen(B+1);
    int l = 0;
    for(int i = 2; i <= a; i++){
        while(l != 0 && A[i] != A[l+1]){
            l = p[l];
        }
        if(A[i] == A[l+1]){
            l++;
        }
        p[i] = l;
    }
    l = 0;
    for(int i = 1; i <= b; i++){
        while(l != 0 && B[i] != A[l+1]){
            l = p[l];
        }
        if(B[i] == A[l+1]){
            l++;
        }
        if(l == a){
            ans++;
            if(ans <= 1000){
                sol.push_back(i-a);
            }
            l = p[l];
        }
    }
    fout << ans << "\n";
    for(int i = 0; i < sol.size(); i++){
        fout << sol[i] << " ";
    }
    return 0;
}