Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence. Solution for https://www.codechef.com/problems/CHEFSQ
#iterative algorithm
def is_sub_seq_iter(sub_seq, seq):
i = 0
j = 0
while i < len(sub_seq) and j < len(seq):
if sub_seq[i] == seq[j]:
i += 1
j += 1
if i == len(sub_seq):
return True
return False
#Recursive algorithm
def is_sub_seq(sub_seq, seq):
if not sub_seq:
return True
if not seq:
return False
if sub_seq[0] == seq[0]:
return is_sub_seq(sub_seq[1:],seq[1:])
else:
return is_sub_seq(sub_seq,seq[1:])
t = int(raw_input())
for i in range(t):
n = int(raw_input())
seq = [int(x) for x in raw_input().split()]
m = int(raw_input())
sub_seq = [int(x) for x in raw_input().split()]
if is_sub_seq_iter(sub_seq,seq):
print "Yes"
else:
print "No"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment