Для приведенного ниже кода, найдите асимптотику:
#include <bits/stdc++.h>
main()
{
std::string s;
std::cin >> s;
int n = s.size(), p[50003], j, i = 1;
for (; i < n; i++)
{
j = p[i - 1];
for (; j && s[i] != s[j]; j = p[j - 1]);
p[i] = (s[i] == s[j] ? ++j : j);
}
std::cout << n - p[n - 1];
}
1) O(n^2) 2) O(nsqrt(n)) 3) O(nlogn) 4) O(n)