Z-function O(n) solution


  • 2
    A

    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;
        }
    }
    

  • 0
    P

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


  • 0
    Z

    @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.


  • 0
    A

    @ZhassanB what about the test like "aaa"?


  • 0
    Z

    @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.


  • 0
    M

    @amanchik said in Z-function O(n) solution:

    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;
                }
            }
    

  • 0
    A

    The correct check logic should be

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

Log in to reply
 

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