首页 > ACM题库 > 九度OJ > 九度-1165-字符串匹配[解题代码]
2013
12-13

九度-1165-字符串匹配[解题代码]

题目来源:2008年北京航空航天大学计算机研究生机试真题

题目描述:

    读入数据string[ ],然后读入一个短字符串。要求查找string[ ]中和短字符串的所有匹配,输出行号、匹配字符串。匹配时不区分大小写,并且可以有一个用中括号表示的模式匹配。如“aa[123]bb”,就是说aa1bb、aa2bb、aa3bb都算匹配。

输入:

输入有多组数据。
每组数据第一行输入n(1<=n<=1000),从第二行开始输入n个字符串(不含空格),接下来输入一个匹配字符串。

输出:

输出匹配到的字符串的行号和该字符串(匹配时不区分大小写)。

样例输入:
4
Aab
a2B
ab
ABB
a[a2b]b
样例输出:
1 Aab
2 a2B
4 ABB

java 代码如下:
import java.io.BufferedInputStream;
import java.util.Scanner;
import java.util.regex.Pattern;
public class Main {
	static int n;
	static String str[];
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNextInt()){
			n = s.nextInt();
			str = new String[n];
			for(int i=0; i<n; i++)
				str[i] = s.next();
			String regex =s.next();  //用正则表达式
			Pattern p = Pattern.compile(regex,Pattern.CASE_INSENSITIVE);
			for(int i=0; i<n; i++){
				if(p.matcher(str[i]).matches()){
					System.out.println((i+1)+" "+str[i]);
				}
			}
		}
	}

}

/**************************************************************
	Problem: 1165
	User: coder
	Language: Java
	Result: Accepted
	Time:160 ms
	Memory:15956 kb
****************************************************************/


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  4. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。