Algorithm
Problem link- https://www.spoj.com/problems/FINGP/
FINGP - Fingerprints
Professor Emad Eldin one of the best people in pattern recognition, he asked his students to create a program to check if a special pattern belongs to fingerprints of someone or not.
He said that we can consider that a computer reads the special pattern and the fingerprints as strings, and we can say that the special pattern belongs to the fingerprint if the last substring of the fingerprint string is the same as the special pattern string.
Your task is to help professor Emad students.
Input
The first line of the input contains special pattern string S (1 ≤ |S| ≤ 50). Second line will be a single integer N, the number of fingerprints (1 ≤ N ≤ 10). N lines follow, each line contains fingerprint string F (1 ≤ |F| ≤ 50).
Output
For each test case, print an integer K, the number of fingerprints strings that special pattern string belongs to it. Followed by K lines, each contains the fingerprint string that the special pattern string belongs to it. You should print the fingerprint strings in a lexicographical order. If there is no fingerprint belongs to the special pattern, print "Wrong fingerprints!" instead.
Examples
Input: On 5 Pattern recognatiOn CommOn patterN game organizatiOn lion Output: 2 Pattern recognatiOn organizatiOn
Input: Ze 2 Fingerprint pattern design Output: Wrong fingerprints!
Notes
- String S contains uppercase English letters ('A' - 'Z') and lowercase English letters ('a' - 'z') only.
- All other strings in the input contains uppercase English letters ('A' - 'Z'), lowercase English letters ('a' - 'z') and spaces (' ') only.
- All strings are case sensitive ('A' is not equal to 'a').
- Lexicographical order is defined in following way. When we compare s and t, first we find the leftmost position with differing characters: si ≠ ti. If there is no such position (i.e. s is a prefix of t or vice versa) the shortest string is less. Otherwise, we compare characters si and ti according to their order in alphabet.
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
pattern = raw_input()
T = int(input())
result = []
for _ in range(T):
text = raw_input()
if text.endswith(pattern):
result.append(text)
if len(result) == 0:
print('Wrong fingerprints!')
else:
print(len(result))
for text in sorted(result):
print(text)
Copy The Code &
Try With Live Editor
Input
5
Pattern recognatiOn
CommOn patterN
game
organizatiOn
lion
Output
Pattern recognatiOn
organizatiOn
Demonstration
SPOJ Solution-Fingerprints-Solution in C, C++, Java, Python