Finding Periods

A period of a string is a prefix that can be used to generate the whole string by repeating the prefix. The last repetition may be partial. For example, the periods of abcabca are abc, abcabc and abcabca.

Your task is to find all period lengths of a string.

Example:

Input:  s = "abcabca"
Output: 3 6 7

Approach

Java

import java.util.Arrays;
import java.util.Vector;

public class FindingPeriods {
    public static void main(String[] args) {

        String s = "abcabca";

        int[] res = findingPeriods(s);

        System.out.println(Arrays.toString(res));
    }

    static int[] findingPeriods(String s) {
        int n = s.length();
        int[] zarray = new int[n];
        int x = 0, y = 0;

        Vector<Integer> res = new Vector<>();
        for (int i = 1; i < n; i++) {
            zarray[i] = Math.max(0, Math.min(zarray[i - x],
                         y - i + 1));
            while (i + zarray[i] < n && s.charAt(zarray[i]) ==
                      s.charAt(i + zarray[i])) {
                x = i;
                y = i + zarray[i];
                zarray[i]++;
            }
            if (zarray[i] + i == n)
                res.add(i);
        }
        res.add(n);
        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }

        return ans;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> findingPeriods(string s)
{
    int n = s.size();
    vector<int> zarray(n, 0);
    int x = 0, y = 0;

    vector<int> res;
    for (int i = 1; i < n; i++)
    {
        zarray[i] = max(0, min(zarray[i - x], y - i + 1));
        while (i + zarray[i] < n && s[zarray[i]] == s[i +
                                       zarray[i]])
        {
            x = i;
            y = i + zarray[i];
            zarray[i]++;
        }
        if (zarray[i] + i == n)
            res.push_back(i);
    }
    res.push_back(n);

    return res;
}

int main()
{
    string s = "abcabca";

    vector<int> res = findingPeriods(s);

    for (int i = 0; i < res.size(); i++)
        cout << res[i] << " ";
    return 0;
}