最长公共前缀后缀_最长的前缀和后缀-蒲公英云

最长公共前缀后缀

Problem statement:

问题陈述：

Given a string of character, find the length of longest proper prefix which is also a proper suffix.

给定一个字符串，找到最长适当前缀的长度，这也是一个适当的后缀。

Input:

输入：

First line is T number of test cases. Each test case has one line denoting the string of length less than 100000.

第一行是T个测试用例。每个测试用例都有一行表示长度小于100000的字符串。

Output:

输出：

Print length of longest proper prefix which is also a proper suffix.

打印最长适当前缀的长度，该长度也是适当的后缀。

Examples:

例子：

Input:    
    T = 1
    "abcdabc"
    Output: 
    3
    //as prefix "abc" is the longest proper prefix 
    //present in the string.
    Input:
    T = 1
    "abcdefghijklm"
    Output: 
    0
    //as there is no prefix which is a suffix.
    Input:
    T = 1
    "aaaaaaa"
    Output:
    6
    //as for proper prefix we can't have entire length 
    // as the prefix so only length possible is 6.

Solution Approach

解决方法

1) Brute Force Approach

1)蛮力法

Since the longest proper prefix which is also a suffix cannot be equal to the entire length of the string because it can’t overlap each other, so we break the string from mid-point and start matching left and right string. If they are equal return size of any one string else try for shorter lengths on both sides.

由于最长的正确前缀(也是后缀)不能等于字符串的整个长度，因为它不能相互重叠，因此我们从中点处断开字符串，然后开始匹配左右字符串。如果它们的返回值等于任一字符串的大小，则请尝试在两侧都使用较短的长度。

Pseudo Code:

伪代码：

void solve(string str)
{
    // declare two variable which will used for
    // comparing two halfs of the string.
    int i, j;
    //store length in len variable.
    int len = str.length();
    i = len / 2; // initialise right half.
    j = 0; // initialise left half.
    // check if the right index variable
    // is less than the length of the string.
    while (i < len) {
        // if the left half character is
        // equal to right half characet.
        is(str[i] == str[j])
        {
            // simply incres the pointers to compare next indexes.
            i++;
            j++;
            continue;
        }
        else
        {
            // if the left half character is at start index
            // and it is not equal to right half current
            // character then increase
            if (j == 0) { // right half index.
                i++;
            }
            else { //search for lesser length of the prefix.
                j--;
            }
        }
    }
    return j; //return length of prefix.
}

C++ Implementation:

C ++实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;
    while (t--) {
        cout << "Enter string: ";
        string str;
        cin >> str;
        ll len = str.length();
        // if length is less than one then
        // simply length of lps is 0.
        if (len <= 1) {
            cout << 0 << "\n";
        }
        else {
            ll i = len / 2; // initialise right half.
            ll j = 0; // initialise left half.
            // check if the right index variable is less
            // than the length of the string.
            while (i < len) {
                // if the left half character is equal to
                // right half characet.
                if (str[i] == str[j]) {
                    i++;
                    j++;
                }
                else {
                    // if the left half character is at start index
                    // and it is not equal to right half current
                    // character then increase right half index.
                    if (j == 0)
                        i++;
                    else
                        j--; // search for lesser length of the prefix
                }
            }
            cout << "Longest prefix-suffix length: ";
            cout << j << "\n";
        }
    }
    return 0;
}

Output

输出量

Enter number of test cases: 3
Enter string: abcdabc
Longest prefix-suffix length: 3
Enter string: abcdefghabcdefgh
Longest prefix-suffix length: 8
Enter string: abcdefgh
Longest prefix-suffix length: 0

2) Better approach: Using longest prefix-suffix array of KMP algorithm

2)更好的方法：使用最长的KMP算法前缀-后缀数组

Here we will use an array which represents the length of the longest proper prefix which is also equal to the suffix of the array.

在这里，我们将使用一个数组，该数组代表最长适当前缀的长度，该长度也等于数组的后缀。

Here we use lps[] array which stores the length of a longest proper prefix which is the equal suffix, each index of lps represent the current index lps upto that index comparison, initialize lps[0]=0, since it is not possible to have proper prefix-suffix with one letter then we declare two variable j and i by which we compare the characters.

在这里，我们使用lps []数组，该数组存储最长的适当前缀(等于后缀)的长度，每个lps索引代表直到该索引比较为止的当前索引lps ，初始化lps [0] = 0 ，因为不可能有一个带一个字母的适当前缀后缀，然后我们声明两个变量j和i，通过它们我们比较字符。