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

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

Given a string of characters, find the length of the longest proper prefix which is also a proper suffix.
Example:
S = abab
LPs are 2 because, ab.. is prefixed and ..ab is also a suffix.

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

Input:
2
abab
aaaa

Output:
2
3

For Input:

3

wrwbwrqwhwrwbw

azwkhazwdazwkhaqazwkhazwdacazwkhazwdazwkhaqazwkhaxazwkhazwdazwkhaqazwkhazwdacazwkhazw

luulufluulluulufluu

Your Output is:

5

35

9

//initial value of character have no prefix and suffix

//update the length of character prefix and suffix

//if j not zero then update previous value

//if j is equal to zero ,so there is no any prefix or suffix

#include <bits/stdc++.h>

using namespace std;

int main() {
    //code
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.size(), a[n], j = 0, i = 1;
        a[0] = 0; 
        while (i < n) {
            if (s[i] == s[j]) 
            {
                a[i] = j + 1;
                ++j, ++i;
            } else {
                if (j != 0) 
                {
                    j = a[j - 1];
                } else {
                    a[i] = 0; 
                    ++i;
                }
            }
        }
        cout << a[n - 1] << endl;

    }

    return 0;
}