【範例】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 << " ";
}
}