Cod sursa(job #2347641)

Utilizator tester_100Alin Barosanu tester_100 Data 18 februarie 2019 22:36:50
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>
#define nmax 2000005

using namespace std;

int N, M;

char B1[nmax], B2[nmax];

class Solution {
    private:

    inline vector<int> computePrefs(char A[]) {
        int lg = strlen(A);
        vector<int> pref(lg + 1);
        return pref;
        for (int i = 2; i <= lg; ++i) {
            int left = pref[i - 1];
            while(left > 0 && A[left] != A[i - 1]) {
                left = pref[left];
            }

            if (A[left] == A[i-1]) {
                pref[i] = left + 1;
            }
        }

        return pref;
    }

    public:
    inline void read() {
        cin >> B1+1 >> B2+1;
    }
    inline void solve() {
        vector<int>pref = computePrefs(B1 + 1);
        int lg = strlen(B2 + 1);
        int sol = 0;
        vector<int> poz;
        int p = 1;
        for(int i = 1; i <= lg; ++i) {
            if (B2[i] == B1[p]) {
                p++;
                if(p-1 == strlen(B1 + 1)) {
                    sol++;
                    poz.push_back(i-p+1);
                    p = pref[p-1] + 1;
                }
                continue;
            }
            while(p > 0 && B2[i] != B1[p]) {
                p = pref[p];
            }
            if(p == 0) {
                p = 1;
            }
            if (p > 0 && B2[i] == B1[p]) {
                p++;
            }

        }
        cout << sol << "\n";
        for(auto it: poz) {
            cout << it << " ";
        }
        cout << "\n";
    }
};

int main(){
    int i;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
//    ios::sync_with_stdio(false);
    Solution sol;
    sol.read();
    sol.solve();
    return 0;
}