串的模式匹配

给定两个由英文字母组成的字符串 String 和 Pattern，要求找到 Pattern 在 String 中第一次出现的位置，并将此位置后的 String 的子串输出。如果找不到，则输出“Not Found”。

本题旨在测试各种不同的匹配算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据0：小规模字符串，测试基本正确性；
• 数据1：随机数据，String 长度为 10​^5，Pattern 长度为 10；
• 数据2：随机数据，String 长度为 10^5，Pattern 长度为 10^2；
• 数据3：随机数据，String 长度为 10^5，Pattern 长度为 10^3；
• 数据4：随机数据，String 长度为 10^5，Pattern 长度为 10^4；
• 数据5：String 长度为 10^6，Pattern 长度为 10^5；测试尾字符不匹配的情形；
• 数据6：String 长度为 10^6，Pattern 长度为 10^5；测试首字符不匹配的情形。

输入格式:

输入第一行给出 String，为由英文字母组成的、长度不超过 1 的字符串。第二行给出一个正整数 N（≤），为待匹配的模式串的个数。随后 N 行，每行给出一个 Pattern，为由英文字母组成的、长度不超过 1 的字符串。每个字符串都非空，以回车结束。

输出格式:

对每个 Pattern，按照题面要求输出匹配结果。

输入样例:

abcabcabcabcacabxy
3
abcabcacab
cabcabcd
abcabcabcabcacabxyz

 

输出样例:

abcabcacabxy
Not Found
Not Found

方法一：

#include <bits/stdc++.h>
char str[1000000];
char str1[1000000];
using namespace std;
int main()
{
    cin>>str;
    int n;
    cin>>n;
    char *p;
    for(int i=0;i<n;i++)
    {
        cin>>str1;
        if(p=strstr(str,str1))
            printf("%s
",p);
        else
            printf("Not Found
");
    }
} 

注意：1、include<bits/stdc++.h> 包含所有的可用到的C++库函数，缺点是会增加编译时间，且可能在一些编译器上无法编译，比如MSVC；

　　　2、strstr(s1,s2)；查找s2在s1中第一次出现的位置。

方法2：

package KMP;

import java.util.Scanner;

public class Main {
    public static int[] getNext(String ps) {
        char[] p = ps.toCharArray();
        int[] next = new int[p.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < p.length - 1) {
            if (k == -1 || p[j] == p[k]) {
                if (p[++j] == p[++k])// 当两个字符相等时要跳过
                    next[j] = next[k];
                else
                    next[j] = k;
            } else
                k = next[k];
        }
        return next;
    }

    public static int KMP(String ts, String ps) {
        char[] t = ts.toCharArray();
        char[] p = ps.toCharArray();
        int i = 0; // 主串的位置
        int j = 0; // 模式串的位置
        int[] next = getNext(ps);
        while (i < t.length && j < p.length) {
            if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0
                i++;
                j++;
            } else
                // i不需要回溯了
                // i = i - j + 1;
                j = next[j]; // j回到指定位置
        }
        if (j == p.length)
            return i - j;
        else
            return -1;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String ts = in.next();
        char[] tsChar = ts.toCharArray();
        int num = in.nextInt();
        String ps[] = new String[10];
        for (int i = 0; i < num; i++)
            ps[i] = in.next();
        int result[] = new int[10];
        for (int i = 0; i < num; i++) {
            result[i] = KMP(ts, ps[i]);
        }
        for (int i = 0; i < num; i++) {
            if (result[i] == -1) {
                System.out.println("Not Found");
            } else {
                for (int j = result[i]; j < ts.length(); j++) {
                    System.out.print(tsChar[j]);
                }
                System.out.println();
            }
        }
    }
}

不明白为啥本地测试几个数据都行，而OJ总是显示WA。。。。。