# Z-function O(n) solution

• To solve this problem there was used z-function algorithm. Which calculates for each position how many characters starting from this position matches the prefix. Algorithm works in O(n) time;
To check if there all characters are period we should check two conditions:

1. the length of prefix + zfunction value must be equal to the size of str. ( it will guarantee that exactly all elements exists in period
2. does characters between (i -- i+z[i]) and prefix covers all characters.

I feel that there exists more elegant check for periods by using the z-function. Any ideas about that?

``````public class Solution {
public boolean repeatedSubstringPattern(String str) {
int n = str.length();
int z[] = zFunction(str.toCharArray());

for (int i=0; i<z.length; i++) {
if (i+z[i]==n && z[i]*2>=str.length()) {
return true;
}
}
return false;
}

private int [] zFunction(char c[]) {
int n = c.length;
int z[] = new int[n];

int left = 0;
int mostRight = 0;

for (int i=1; i<n; i++) {
if (i<=mostRight) {
z[i] = Math.min(mostRight-i+1, z[i-left]);
}
while (i+z[i]<n && c[i+z[i]] == c[z[i]]) {
z[i]++;
}
if (i+z[i]-1>mostRight) {
mostRight = i+z[i]-1;
left = i;
}
}
return z;
}
}
``````

• @amanchik why we need a check of 'z[i]*2>=str.length()' ?

• @amanchik Here one more simple optimization can be done. Take the last value of the z function, then check whether that is not zero and whether that value divides the length of original string evenly. If the latter condition fails, you may immediately output false.

• @ZhassanB what about the test like "aaa"?

• @amanchik Can we modify z function so that it doesn't count overlapping characters? If we can, then it is ok, you check z[n-1] != 0 && n%z[n-1] == 0 which will be true.

• re exists more elegant check for periods by using the z-funct

I think this is enough:

``````        for (int i = 1; i <= n/2; i++) {
if (i+z[i]==n) {
return true;
}
}
``````

• The correct check logic should be

``````        for (int i = 1; i <= n/2; i++) {
if (z[n-i]+z[i]==n) {
return true;
}
}
``````

• The above code fails in this test case "aabaaba". Its answer is true, while the expected answer is false.
I have corrected it. The idea of the following code is from: https://discuss.leetcode.com/topic/67652/c-o-n-using-kmp-32ms-8-lines-of-code-with-brief-explanation)

``````class Solution {
public:
bool repeatedSubstringPattern(string s) {
vector<size_t> z(s.size());
size_t L = 0, R = 0, n = s.size();
for (size_t i = 1; i < n; ++i) {
if (i <= R)
z[i] = min(z[i - L], R - i + 1);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] - 1 > R)
L = i, R = i + z[i] - 1;
if (z[i] + i == n && n % (n - z[i]) == 0) return true; // Here
}
return false;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.