Longest Common Suffix
MediumPractice library · +20 XPstringshashingsuffix array
Given two strings, S1 and S2, find the length of their longest common suffix. The common suffix must be non-empty.
Input
Two lines of input, each containing a string S1 and S2 respectively. Strings consist of lowercase English letters.
Output
A single integer representing the length of the longest non-empty common suffix. If there is no common suffix, output 0.
Constraints
1 <= |S1|, |S2| <= 200000
Time limit 2 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
apple dimple
Output
3
The longest common suffix is 'ple', length 3.
Example 2
Input
banana bandana
Output
3
The longest common suffix is 'ana', length 3.
Hints
Similar problems
- Most Frequent SubstringMedium
- String PartitionMedium
- Longest Substring With At Most K Distinct CharactersMedium
- Longest Prefix With No RepeatsMedium
- String with Most Unique CharactersMedium
- Longest Substring Without RepeatsMedium
More topics: Strings problems, Hash Map and Hashing problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
apple dimple
Example 2 input
banana bandana