2013
11-12

# Subsequence

Given a string s of length n, a subsequence of it, is defined as another string s’ = su1su2…sum where 1 ≤ u1 < u2 < … < umn and si is the ith character of s. Your task is to write a program that, given two strings s1 and s2, checks whether either s2 or its reverse is a subsequence of s1 or not.

The first line of input contains an integer T, which is the number of test cases. Each of the next T lines contains two non-empty strings s1 and s2 (with length at most 100) consisted of only alpha-numeric characters and separated from each other by a single space.

For each test case, your program must output "YES", in a single line, if either s2 or its reverse is a subsequence of s1. Otherwise your program should write "NO".

5
arash aah
arash hsr
kick kkc
A a
a12340b b31

YES
YES
NO
NO
YES

//* @author 洪晓鹏<[email protected]>
import java.util.Scanner;

public class Main {

/**
* @param args
*/
public static boolean isSubsequence(String s1, String s2) {
int len = s2.length();
int index = -1;
int i = 0;
for (i = 0; i < len; i++) {
index = s1.indexOf(s2.charAt(i), index + 1);
if (index == -1) {
break;
}
}
if (i == len && index != -1)
return true;
index = -1;
for (i = len; i > 0; i--) {
index = s1.indexOf(s2.charAt(i - 1), index + 1);
if (index == -1)
break;
}
if (i == 0 && index != -1)
return true;
return false;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int num = in.nextInt();
for (int i = 0; i < num; i++) {
String s1 = in.next();
String s2 = in.next();
if (isSubsequence(s1, s2)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}

}

1. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.