class Solution {
public:
    int minimumTimeToInitialState(string word, int k) {
        int n=word.size();
        std::vector<int>z(n);
        for(int i=1,r=0,c=0;i<n;i++){
            int len=(r>i?std::min(r-i,z[i-c]):0);
            while(i+len<n&&word[i+len]==word[len])++len;
            if(i+len>r)r=i+len,c=i;
            if(i%k==0&&i+len==n){
                return i/k;
            }
            z[i]=len;
        }
        return (n+k-1)/k;
    }
};