最长公共前缀后缀_最长的前缀和后缀

桃扇骨 2023-03-05 09:52 24阅读 0赞

最长公共前缀后缀

**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，***通过它们我们比较字符。

**Pseudo Code:**

**伪代码：**

int longestprefix(string str)
    {
        int len = str.length(); //len variable stores length of string.
        int lps[len]; //declare lps array.
        lps[0] = 0; //single charater case so length lps is 0.
        int i = 1; //initialise index for comparison from 1.
        int j = 0; //initial longest prefix suffix length.
        while (i < len) //check until i!=len of string.
        {
            //check current index character with character stored at j.
            if (str[i] == str[j]) {
                j++; //increase length by one.
                lps[i] = j; //lps for current index is equal to j
                i++; //move forward.
            }
            else //if str[i]!=str[j]
            {
                //we search for that index which character matches
                //with the current character at index i.
                if (j != 0) {
                    j = lps[j - 1];
                }
                else {
                    lps[i] = 0;
                    i++;
                } //if j==0 then lps[i]=0.
            }
        }
        return lps[j - 1]; //return lcs of given string.
    }

**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(); //len variable stores length of string.
            ll lps[len]; //declare lps array.
            lps[0] = 0; //single charater case so length lps is 0.
            ll i, j;
            i = 1; //initialise index for comparison from 1.
            j = 0; //initial longest prefix suffix length.
    
            while (i < len) //check until i!=len of string.
            {
        
                //check current index character with character stored at j.
                if (str[i] == str[j]) 
                {
        
                    j++; //increase length by one.
                    lps[i] = j; //lps for current index is equal to j
                    i++; //move forward.
                }
                else //if str[i]!=str[j]
                {
        
                    //we search for that index which character matches 
                    //with the current character at index i.
                    if (j != 0) 
                        j = lps[j - 1];
                    else {
        
                        lps[i] = 0; //if j==0 then lps[i]=0.
                        i++; //move forward.
                    }
                }
            }
            cout << "Maximum length of proper prefix-suffix: ";
            cout << lps[len - 1] << "\n";
        }
    
        return 0;
    }

**Output:**

**输出：**

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

*  Time Complexity for above approach is: **O(n)**
    
    上述方法的时间复杂度为： **O(n)**
 *  Space Complexity for above approach is: **O(n)**
    
    上述方法的空间复杂度为： **O(n)**

--------------------

Problem reference: https://practice.geeksforgeeks.org/problems/longest-prefix-suffix/0

问题参考：https：//practice.geeksforgeeks.org/problems/longest-prefix-suffix/0

> 翻译自: [https://www.includehelp.com/icp/longest-prefix-and-suffix.aspx][https_www.includehelp.com_icp_longest-prefix-and-suffix.aspx]

最长公共前缀后缀

[https_www.includehelp.com_icp_longest-prefix-and-suffix.aspx]: https://www.includehelp.com/icp/longest-prefix-and-suffix.aspx