【題解】CSES 1732 Finding Borders

【範例】Z-Algorithm(例1)
【題目敘述】https://cses.fi/problemset/task/1732

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int z[1000005];
vector <int> ans;
string s;
 
int main() {
    cin >> s;
    z[0] = s.length();
    int l = 0, r = 0;
    for (int i = 1; i < s.length(); i++){
        if (i <= r && z[i-l] < r-i+1) z[i] = z[i-l];
        else{
            l = i;
            if (i > r){
                r = i;
            }
            while (r < s.length() && s[r-l] == s[r]) r++;
            r--;
            z[l] = r-l+1;
        }
        if (z[i] == s.length()-i) ans.push_back(s.length()-i);
    }
    reverse(ans.begin(), ans.end());
    for (auto i:ans){
        cout << i << " ";
    }
}
分享本文 Share with friends