Interview Question - use kmp

Given a string S, you are allowed to convert it to a palindrome by adding 0 or more characters in front of it.
Find the length of the shortest palindrome that you can create from S by applying the above transformation.

Answer:

Best solution here is to use a Knuth-Morris-Pratt algorithm. It runs in O(n) time, requires 2*n additional space and extremely fast and easy to code. The main idea is - we construct new string that contains our string + some symbol that can't be in our string, for instance '$' + reversed our string. After that we need to run KMP for that string to calculate prefix function. The answer is the length of our starting string minus prefix function value of the last element of the new string.

prefix function for every position i in the string shows the maximum length of prefix for the string s [0...i] that equals to suffix of the string s[0...i].
So if we construct new string in the way described above, prefix function for the last element will show the maximum size of the palindrome in the beginning of our string. All we have to do is to add in front of our string the rest of the characters.

int getPalindrome(string s) {
    int n = s.size();

    vector<int> p(2*n+1,0); 

    string current = s + '$';

    for (int i = 0; i < n; i++) {
        current += s[n - 1 - i];
    }

    p[0] = 0;
    for (int i = 1; i < 2 * n + 1; i++) {
        int j = p[i - 1];
        while (j > 0 && current[j] != current[i])
            j = p[j - 1];
        j += current[i] == current[j];
        p[i] = j;
    }
    return 2 *n - p[2 * n];//returns the length of the palindrome formed
}

string question: example using kmp

A家的电面题:

有一种String,是把一个更短的String重复n次而构成的，那个更短的String长度至少为
2，输入一个String写代码返回T或者F
例子：
"abcabcabc"  Ture   因为它把abc重复3次构成
"bcdbcdbcde" False  最后一个是bcde
"abcdabcd"   True   因为它是abcd重复2次构成
"xyz"       False  因为它不是某一个String重复
"aaaaaaaaaa"  False  重复的短String长度应至少为2（这里不能看做aa重复5次)

要求算法复杂度为O(n)

public boolean isMultiple(String s){

}


Ans:

用KMP吧。检查preprocess部分生产的array pai 就可以了。如果是valid case.
preprocessing array 必然满足下面的几个条件：
1. pai[n-1] 必须是最大值 (这个没必要专门检查,只要3满足就成);
2. s[0,...,n-pai[n-1])就是repeating pattern;
3. pai[n-1]/(length of the repeating pattern) >= 1;
4. pai[n-1] % (length of the repeating pattern) == 0.

bool isMultiple(const string &text){
    int n=text.length();
    vector<int> pai(n);
    computeVec(text,pai);
    int len=n-pai[n-1];
    return len>1&&pai[n-1]/len>=1&&pai[n-1]%len==0;
}

void computeVec(const string &Pat, vector<int>&pai){//from KMP
    pai[0]=0;
    int k=0;
    int m=Pat.length();
    for(int i=1;i<m;i++){
        while(k>0&&Pat[k]!=Pat[i])
            k=pai[k-1];
        if(Pat[k]==Pat[i])
            k++;
        pai[i]=k;
    }
}

kmp string match

from CLRS(Introduction to Algorithm)

For a pattern P, pai[q] is the length of the longest prefix of P that is a proper suffix of Pq. (Pq is P[1...q], note that here the index start from 1, which is different from the code below)

vector<int> computepai(string Pat){
    int n=Pat.length();
    vector<int> pai(n,0);
    pai[0]=0;

    for(int i=1;i<n;i++){
        int k=pai[i-1];//number of characters matched
        while(k>0&&Pat[k]!=Pat[i])
            k=pai[k-1];
        k+=Pat[k]==Pat[i];

        pai[i]=k;
    }
    return pai;
}

下面这个computepai是算法导论上的版本，和上面的几乎一样（不同的只是k的位置），但是上面的似乎更容易理解和记忆些。
vector<int> computepai(string Pat){
    int n=Pat.length();
    vector<int> pai(n,0);
    pai[0]=0;
    int k=0;//number of characters matched
    for(int i=1;i<n;i++){
        while(k>0&&Pat[k]!=Pat[i])
            k=pai[k-1];
        if(Pat[k]==Pat[i])
            k++;
        pai[i]=k;
    }
    return pai;
}

void matchstr(string text,string Pat){
    int n=text.length();
    int m=Pat.length();
    vector<int> pai= computepai(Pat);
    int k=0;//number of characters matched
    for(int i=0;i<n;i++){//scan the text from left to right
        while(k>0&&Pat[k]!=text[i])
            k=pai[k-1];   //next character of P doesn't match text[i]
        if(Pat[k]==text[i])
            k++;       //next character matches
        if(k==m){  // is all of P matched
            cout<<"find in pos : "<<i-m+1<<"  "<<text.substr(i-m+1,m)<<endl;
            k=pai[k-1];
        }
    }
}