Cod sursa(job #3146614)

Utilizator nnmadalinNeauna Madalin nnmadalin Data 21 august 2023 21:07:49
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define tie_ion_base cin.tie(NULL);ios_base::sync_with_stdio(false);

#define int long long 

#define cin fin
#define cout fout

const string FILE_NAME = "strmatch";
ifstream fin(FILE_NAME + ".in");
ofstream fout(FILE_NAME + ".out");

vector<int> lps(string a){
    vector <int> v(a.size(), 0);

    int len = 0;
    
    for(int i = 1; i < a.size();){
        if(a[i] == a[len]){
            len++;
            v[i] = len;
            i++;
        }
        else{
            if(len != 0){
                len = v[len - 1];
            }
            else
                a[i] = 0;
            i++;
        }
    }

    return v;
}

signed main()
{
    tie_ion_base;

    string a, b;
    int p = 0, n = 0;
    

    cin >> a >> b;
    
    vector <int> v = lps(a);
    vector <int> array;

    for(int i = 0, j = 0; i < b.size();){
        if(b[i] == a[j]){
            j++;
            i++;
            if(j == a.size()){
                n++;
                if(n < 1000)
                    array.pb(i - j + 1);
                j = v[j - 1];
            }
        }
        else{
            if(j != 0)
                j = v[j - 1];
            else
                i++;
        }
    }

    cout << n << "\n";
    for(int i = 0; i < n && i < 1000; i++){
        cout << array[i] << " ";
    }

    
    return 0;
}