Hello!↵
↵
I have TLE on 23 test with O(n) (I think so) Z-function. I want to reverse origin string and just use Z-func. Where is the problem?↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <string>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
void z_function (string s) {↵
int n = (int) s.length();↵
string str = s;↵
//reverse(str.begin(), str.end());↵
for (int i = 0; i < str.length() / 2; i++) {↵
swap(str[i], str[str.length() — 1 — i]);↵
}↵
s += '#';↵
s += str;↵
n = s.length();↵
//cout << s << '\n';↵
vector<int> z (n);↵
for (int i=str.length() + 1, l=0, r=0; i<n; ++i) {↵
if (i <= r)↵
z[i] = min (r-i+1, z[i-l]);↵
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {↵
//cout << "z[i] = " << z[i] << ' ' << s[i] << ' ' << "i + z[i] = " << i +z[i] << ' ' << s[i +z[i]] << '\n';↵
++z[i];↵
}↵
if (i+z[i]-1 > r)↵
l = i, r = i+z[i]-1;↵
//cout << z[i] << ' ';↵
}↵
↵
int ans = 1;↵
for (int i = str.length() + 1; i < z.size(); i++) ans = max(ans, z[i]);↵
cout << ans;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
↵
string s;↵
cin >> s;↵
int n = s.length();↵
↵
z_function(s);↵
↵
}↵
↵
~~~~~↵
↵
[problem:https://codeforces.net/edu/course/2/lesson/3/4/practice/contest/272262/problem/D]
↵
I have TLE on 23 test with O(n) (I think so) Z-function. I want to reverse origin string and just use Z-func. Where is the problem?↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <string>↵
#include <algorithm>↵
↵
using namespace std;↵
↵
void z_function (string s) {↵
int n = (int) s.length();↵
string str = s;↵
//reverse(str.begin(), str.end());↵
for (int i = 0; i < str.length() / 2; i++) {↵
swap(str[i], str[str.length() — 1 — i]);↵
}↵
s += '#';↵
s += str;↵
n = s.length();↵
//cout << s << '\n';↵
vector<int> z (n);↵
for (int i=str.length() + 1, l=0, r=0; i<n; ++i) {↵
if (i <= r)↵
z[i] = min (r-i+1, z[i-l]);↵
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {↵
//cout << "z[i] = " << z[i] << ' ' << s[i] << ' ' << "i + z[i] = " << i +z[i] << ' ' << s[i +z[i]] << '\n';↵
++z[i];↵
}↵
if (i+z[i]-1 > r)↵
l = i, r = i+z[i]-1;↵
//cout << z[i] << ' ';↵
}↵
↵
int ans = 1;↵
for (int i = str.length() + 1; i < z.size(); i++) ans = max(ans, z[i]);↵
cout << ans;↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
↵
string s;↵
cin >> s;↵
int n = s.length();↵
↵
z_function(s);↵
↵
}↵
↵
~~~~~↵
↵
[problem:https://codeforces.net/edu/course/2/lesson/3/4/practice/contest/272262/problem/D]
