**Problem**

Given a string ‘S’, find the longest proper prefix that is also a suffix of ‘S’. You have to print the size of the longest proper prefix.

**Note:** A string’s proper prefix includes all prefixes except the entire string itself.

**Examples**

**Input: **‘S’ = xyxyxy

**Output:** 4

**Explanation:**

The prefix of length 4 is ‘xyxy’, and the suffix of length 4 is ‘xyxy’. Therefore the prefix of length 4 is valid. If we take a length equal to 5, the prefix will be ‘xyxyx’ while the suffix will be ‘yxyxy’. These are not equal, so the prefix of length 5 is not valid. We can’t take a prefix of length 6, as that will contain the entire string (it will not be a proper prefix).

Therefore, the longest proper prefix that is also a suffix has length 4.

**Input: **‘S’ = abcab

**Output:** 2

**Explanation:**

The longest proper prefix that is also a suffix for the above example is ‘ab’.

**Naive Approach**

We can iterate over the length of the proper prefix and check if it matches the suffix of the same length. If it matches, we will update our answer. Thus, in the end, we will get the length of the longest proper prefix that is also a suffix.

**Implementation**

```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
/*
Function to find the length of
Longest proper prefix that is also a suffix.
*/
void solve(string s){
int ans = 0;
int n = s.size();
// Iterating over the length of prefix
for (int l = 1; l<=n-1; l++){
string prefix = "";
string suffix = "";
// Storing prefix of the given length
for(int i=0; i<l; i++){
prefix += s[i];
}
// Storing suffix of the given length
for(int i=n-l; i<n; i++){
suffix += s[i];
}
// If prefix and suffix are same, update answer
if (prefix == suffix){
ans = l;
}
}
// Printing the longest proper prefix that is also a suffix.
cout<<ans<<endl;
}
// Driver Code
int main(){
string s = "xyxyxy";
solve(s);
}
```

**Output:**

`4`

**Time Complexity: O(N ^ 2)**

We are first iterating over the length of the prefix, which will take O(N) time. For each length value, we create corresponding prefixes and suffixes and check if they are equal. This will again take O(N) time. Therefore the total time complexity of the above approach is O(N ^ 2).

**Space Complexity: O(N)**

For each value of the length of the prefix, we are creating a corresponding prefix and suffix. This will take O(N) space. Therefore, the space complexity of the above approach is O(N).

Also check out - __Substr C++____ __and __Rabin Karp Algorithm__