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

include

include

include

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 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]