Expert.
Put your skills to the test.

Problem summary

Given k cyclic strings of the same length n, find the longest ordinary string that occurs as a contiguous cyclic substring of all of them. A cyclic substring may wrap around once and has length at most n.

Constraints

1 ≤ n ≤ 100000; 2 ≤ k ≤ 10.

Worked example

Official example, transcribed with whitespace restored from the PDF.

5 2
fabcq
bcdda

3

Solution analysis

1. Every cyclic substring of length at most n appears in the doubled ordinary string s+s. Build a suffix automaton for the first doubled string. A state represents substring lengths from len(link(state))+1 through len(state). Initialize its common-length bound to len(state).
2. For every other doubled string, scan it through the automaton, maintaining the length of the longest suffix that occurs in the first string. Record the largest match length ending in each state. Then process states in decreasing length, propagating min(match[state],len[parent]) to their suffix-link parents. This records the best occurrence for every state, including suffixes that were not explicit scan endpoints. Intersect the state bounds by taking their minimum with these propagated matches.
3. The largest final bound, capped at n, is the answer. For the example, abc occurs directly in fabcq and wraps from the final a of bcdda to its initial bc, giving length three.

Why it works

Doubling realizes exactly all permitted cyclic substrings once lengths are restricted to at most n. The automaton scan records the longest matching suffix after each input position. Suffix-link propagation accounts for every shorter suffix represented by ancestor states, so each state’s bound is the greatest represented length occurring in that input. Taking minima across inputs retains precisely lengths occurring in every doubled string. Maximizing those bounds and capping at n therefore gives exactly the longest common permitted cyclic substring.

Watch out. The answer itself is an ordinary substring; do not compare its rotations. Cap the answer at n and propagate matches down suffix links before intersecting.

An independently written complete program with standard headers.

// Key idea: Doubling realizes exactly all permitted cyclic substrings once lengths are restricted to
// at most n. The automaton scan records the longest matching suffix after each input position.
#include<algorithm>
#include<array>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct State{
    array<int,26>next;
    int link=-1;
    int length=0;
    State(){
        next.fill(-1);
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    string first;
    cin>>first;
    vector<State>states(1);
    states.reserve(4*n);
    int last=0;
    auto extend=[&](int c){
        int current=static_cast<int>(states.size());
        states.emplace_back();
        states[current].length=states[last].length+1;
        int p=last;
        while(p!=-1&&states[p].next[c]==-1){
            states[p].next[c]=current;
            p=states[p].link;
        }
        if(p==-1){
            states[current].link=0;
        }
        else{
            int q=states[p].next[c];
            if(states[p].length+1==states[q].length){
                states[current].link=q;
            }
            else{
                int clone=static_cast<int>(states.size());
                states.push_back(states[q]);
                states[clone].length=states[p].length+1;
                while(p!=-1&&states[p].next[c]==q){
                    states[p].next[c]=clone;
                    p=states[p].link;
                }
                states[q].link=states[current].link=clone;
            }
        }
        last=current;
    };
    for(int repetition=0;repetition<2;++repetition){
        for(char c:first){
            extend(c-'a');
        }
    }
    int size=static_cast<int>(states.size());
    vector<int>count(2*n+1),order(size),common(size);
    for(int v=0;v<size;++v){
        ++count[states[v].length];
        common[v]=states[v].length;
    }
    for(int i=1;i<=2*n;++i){
        count[i]+=count[i-1];
    }
    for(int v=size-1;v>=0;--v){
        order[--count[states[v].length]]=v;
    }
    for(int input=1;input<k;++input){
        string text;
        cin>>text;
        vector<int>match(size);
        int v=0,length=0;
        for(int repetition=0;repetition<2;++repetition){
            for(char character:text){
                int c=character-'a';
                while(v!=0&&states[v].next[c]==-1){
                    v=states[v].link;
                    length=min(length,states[v].length);
                }
                if(states[v].next[c]!=-1){
                    v=states[v].next[c];
                    ++length;
                }
                else{
                    v=0;
                    length=0;
                }
                match[v]=max(match[v],length);
            }
        }
        for(int i=size-1;i>0;--i){
            int child=order[i];
            int parent=states[child].link;
            match[parent]=max(match[parent],min(match[child],states[parent].length));
        }
        for(int state=0;state<size;++state){
            common[state]=min(common[state],match[state]);
        }
    }
    cout<<min(n,*max_element(common.begin(),common.end()))<<'\n';
}