Algorithm

Problem link- https://www.spoj.com/problems/FINGP/

FINGP - Fingerprints

no tags 

 

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

x
–
+
cmd
On
5
Pattern recognatiOn
CommOn patterN
game
organizatiOn
lion

Output

x
–
+
cmd
2
Pattern recognatiOn
organizatiOn
Advertisements

Demonstration

SPOJ Solution-Fingerprints-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python