Given a string of characters, find the length of the longest proper prefix which is also a proper suffix.
NOTE: Prefix and suffix can be overlapping but they should not be equal to the entire string.
Example 1:
Input: s = "abab"
Output: 2
Explanation: "ab" is the longest proper 
prefix and suffix. 
Example 2:
Input: s = "aaaa"
Output: 3
Explanation: "aaa" is the longest proper 
prefix and suffix. 
Your task:
You do not need to read any input or print anything. The task is to complete the function lps(), which takes a string as input and returns an integer. 
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(|s|)
Constraints:
1 ≤ |s| ≤ 10^{5}
s contains lower case English alphabets

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

	def lps(self, s):

		# code here

Solutions:
class Solution:

	def lps(self, s):
		lps = [0] * len(s)
		(prevLPS, i) = (0, 1)
		while i < len(s):
			if s[prevLPS] == s[i]:
				lps[i] = prevLPS + 1
				prevLPS += 1
				i += 1
			elif prevLPS == 0:
				lps[i] = 0
				i += 1
			else:
				prevLPS = lps[prevLPS - 1]
		return lps[-1]


class Solution:

	def lps(self, s):
		n = len(s)
		k = 0
		j = 1
		while j + k < n:
			if s[k] == s[j + k]:
				k += 1
			else:
				j += 1
				k = 0
		return k


class Solution:

	def lps(self, pat):
		n = len(pat)
		lps = [0] * n
		le = 0
		i = 1
		lps[0] = 0
		while i < n:
			if pat[i] == pat[le]:
				le += 1
				lps[i] = le
				i += 1
			elif le != 0:
				le = lps[le - 1]
			else:
				lps[i] = 0
				i += 1
		return lps[n - 1]


class Solution:

	def lps(self, string):
		first = 0
		second = 2
		Lps_arr = [0] * (len(string) + 1)
		string = ' ' + string
		while second < len(string):
			if string[first + 1] == string[second]:
				Lps_arr[second] = first + 1
				first += 1
				second += 1
			elif first != 0:
				first = Lps_arr[first]
			else:
				second += 1
		return Lps_arr[-1]


class Solution:

	def lps(self, s):
		if s[0] * len(s) == s:
			return len(s) - 1
		i = 0
		if len(s) % 2 == 0:
			mid = len(s) // 2
		else:
			mid = len(s) // 2 + 1
		j = 1
		count = 0
		k = 1
		while i < len(s) - 1 and j < len(s):
			if s[i] == s[j]:
				count += 1
				i += 1
				j += 1
			else:
				i = 0
				k += 1
				j = k
				count = 0
		return count


class Solution:

	def lps(self, s):
		(i, j, k, cnt) = (0, 1, 1, 0)
		n = len(s)
		while i < n - 1 and j < n:
			if s[i] == s[j]:
				cnt = cnt + 1
				i = i + 1
				j = j + 1
			elif s[i] != s[j]:
				i = 0
				k = k + 1
				cnt = 0
				j = k
		return cnt


class Solution:

	def lps(self, s):
		n = len(s)
		ans = 0
		fli = []
		for i in range(1, n):
			if s[i] == s[0]:
				fli.append(i)
		for i in fli:
			if s[i:] == s[:n - i]:
				ans = n - i
				break
		return ans


class Solution:

	def lps(self, s):
		n = len(s)
		lps = [0] * n
		(i, j) = (1, 0)
		while i < n:
			if s[i] == s[j]:
				lps[i] = j + 1
				i += 1
				j += 1
			elif j != 0:
				j = lps[j - 1]
			else:
				lps[i] = 0
				i += 1
		return lps[-1]


class Solution:

	def lps(self, s):
		lps = [0 for i in range(len(s))]
		j = 1
		i = 0
		maxi = 0
		while j < len(s):
			if s[i] == s[j]:
				lps[j] = i + 1
				j += 1
				i += 1
			elif i == 0:
				j += 1
			else:
				i = lps[i - 1]
		return lps[-1]


class Solution:

	def lps(self, s):
		n = len(s)
		pi = [0] * n
		j = 0
		for i in range(1, n):
			while j > 0 and s[i] != s[j]:
				j = pi[j - 1]
			if s[i] == s[j]:
				j += 1
			pi[i] = j
		return pi[-1]


class Solution:

	def lps(self, s):
		n = len(s)
		for i in range(n - 1, 0, -1):
			for j in range(i):
				if s[j] != s[n - i + j]:
					break
			else:
				return i
		return 0


class Solution:

	def lps(self, s):
		if len(s) == 0:
			return 0
		if len(s) == 1:
			return 1
		b = ''.join(sorted(s))
		if b[0] == b[len(b) - 1]:
			return len(b) - 1
		i = 0
		j = 1
		n = len(s)
		count = 0
		while j < n:
			count = 0
			if s[j] == s[i] and i + (j - n - 1) < j:
				ii = i
				jj = j
				while jj < n:
					if s[ii] != s[jj]:
						break
					ii += 1
					jj += 1
					count += 1
				if jj == n:
					return count
			j += 1
		return count


class Solution:

	def lps(self, s):
		arr = [0] * len(s)
		j = 0
		if len(s) == 1:
			return 0
		i = 1
		while i < len(s):
			if s[i] == s[j]:
				arr[i] = j + 1
				j += 1
				i += 1
			else:
				if j != 0:
					j = arr[j - 1]
				if j == 0 and s[i] != s[j]:
					arr[i] = 0
					i += 1
		return arr[-1]


class Solution:

	def lps(self, S):
		lenpf = 0
		i = 1
		lps = [0 for i in range(len(S))]
		while i < len(S):
			if S[i] == S[lenpf]:
				lps[i] = lenpf + 1
				lenpf += 1
				i += 1
			elif lenpf != 0:
				lenpf = lps[lenpf - 1]
			else:
				lps[i] = 0
				i += 1
		return lps[len(S) - 1]


class Solution:

	def lps(self, s):
		n = len(s)
		if n == 1:
			return 0
		ele = s[0]
		gle = s[-1]
		i = 1
		j = n - 2
		ans = 0
		str = ''
		while i < n and j > 0:
			if s[j] == gle:
				str = s[0:j + 1]
			j -= 1
			if s[i] == ele and s[i:] == str:
				ans = max(ans, n - i)
				return ans
			i += 1
		if n > 1 and ele == gle and (ans == 0):
			return 1
		return ans


import string

class Solution:

	def lps(self, s):
		n = len(s)
		i = n - 1
		j = 1
		x = ''
		y = ''
		while j < n and i >= 0:
			if s[0] != s[j]:
				i -= 1
				j += 1
				continue
			x = s[:i]
			y = s[j:]
			if x == y:
				return i
			i -= 1
			j += 1
		return 0


class Solution:

	def lps(self, s):
		l = len(s)
		l1 = [i for i in range(l) if s[i] == s[0]]
		n = len(l1)
		if n > 1:
			for i in range(1, n):
				d = l - l1[i]
				a = s[:d]
				b = s[l1[i]:]
				if a == b:
					return d
			return 0
		return 0


class Solution:

	def lps(self, s):
		arr = [0] * len(s)
		(i, l) = (1, 0)
		while i < len(s):
			if s[i] == s[l]:
				l += 1
				arr[i] = l
				i += 1
			elif l == 0:
				arr[i] = 0
				i += 1
			else:
				l = arr[l - 1]
		return arr[-1]


class Solution:

	def lps(self, s):
		for substrlen in range(len(s) - 1, 0, -1):
			index = 0
			while True:
				if index == substrlen:
					return substrlen
				if s[index] != s[len(s) - substrlen + index]:
					break
				index += 1
		return 0


class Solution:

	def lps(self, s):
		for index in range(1, len(s)):
			prefixindex = 0
			while index + prefixindex < len(s) and s[prefixindex] == s[index + prefixindex]:
				prefixindex += 1
			if index + prefixindex == len(s):
				return len(s) - index
		return 0


class Solution:

	def lps(self, s):
		arr = []
		n = len(s)
		for i in range(len(s) - 1):
			if s[i] == s[-1]:
				arr.append(i)
		out = float('-inf')
		for i in arr[::-1]:
			if s[:i + 1] == s[n - i - 1:]:
				return i + 1
		return 0


class Solution:

	def lps(self, str):
		A = [0 for i in range(len(str))]
		j = 0
		i = 1
		while i < len(str):
			if str[i] == str[j]:
				A[i] = j + 1
				j += 1
				i += 1
			elif j == 0:
				i += 1
			else:
				j = A[j - 1]
		return A[-1]


class Solution:

	def lps(self, s):
		a = len(s)
		if a == 1:
			return 0
		x = s[0]
		y = s[-1]
		i = 1
		j = a - 2
		r = 0
		str = ''
		while i < a and j > 0:
			if s[j] == y:
				str = s[0:j + 1]
			j -= 1
			if s[i] == x and s[i:] == str:
				r = max(r, a - i)
				return r
			i += 1
		if a > 1 and x == y and (r == 0):
			return 1
		return r


class Solution:

	def lps(self, s):
		n = len(s)
		table = [0] * n
		(i, j) = (1, 0)
		while i < n:
			if s[i] == s[j]:
				table[i] = j + 1
				i += 1
				j += 1
			elif j > 0:
				j = table[j - 1]
			else:
				i += 1
		return table[-1]

	def longest_prefix_suffix(self, s):
		n = len(self.s)
		if n < 2:
			return 0
		length = lps(self.s)
		if length == 0:
			return 0
		if length >= n // 2:
			return n // 2
		return length


class Solution:

	def lps(self, s):
		lp = [0] * len(s)
		(prLPS, i) = (0, 1)
		while i < len(s):
			if s[prLPS] == s[i]:
				lp[i] = prLPS + 1
				prLPS += 1
				i += 1
			elif prLPS == 0:
				lp[i] = 0
				i += 1
			else:
				prLPS = lp[prLPS - 1]
		return lp[-1]


class Solution:

	def lps(self, s):
		j = -1
		p = [j]
		for c in s:
			while j >= 0 and s[j] != c:
				j = p[j]
			j += 1
			p.append(j)
		return len(s[:j])


class Solution:

	def lps(self, s):
		M = len(s)
		arr = [0] * M
		length = 0
		i = 1
		while i < M:
			if s[i] == s[length]:
				length += 1
				arr[i] = length
				i += 1
			elif length != 0:
				length = arr[length - 1]
			else:
				arr[i] = 0
				i += 1
		return arr[-1]