字符串匹配

	





	#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int CH = 36, N = 50007;
struct AC {
    struct Node {
        Node *ch[CH];
        bool end;
        void init() {
            memset(ch, (int)NULL, sizeof(ch));
            end = false;
        }
    };
    Node *root, *que[N];
    Node a[N];
    int p;
    Node* getNewNode() {
        a[p].init();
        return &a[p ++];
    }
    int getindex(char ch) {
        if('0' <= ch && ch <= '9') return ch - '0';
        else return ch - 'a' + 10;
    }
    void init() {
        p = 0;
        root = getNewNode();
    }
    void insert(Node *cur, char *s, bool del) {
        int index;
        while(*s != '\0') {
            if(*s == '[') {
                while(*(++ s) != ']') insert(cur, s, true);
                break;
            } else {
                index = getindex(*(s ++));
                if(cur -> ch[index] == NULL) {
                    cur -> ch[index] = getNewNode();
                }
                cur = cur -> ch[index];
                if(del) {
                    while(*s != ']') s ++;
                    s ++;
                    del = false;
                }
            }
        }
        if(*s == '\0') cur -> end = true; 
    }
    bool run(char *s) {
        Node *cur = root;
        int index;
        while(*s != '\0' && cur) {
            index = getindex(*(s ++));
            cur = cur -> ch[index];
        }
        return cur && cur -> end && *s == '\0';
    }
} ac;
const int maxn = 1007;
string instr, a[maxn], ans[maxn];
char *s;
int main() {
    freopen("input.txt", "r", stdin);
    int i, j, n;
    while(~scanf("%d", &n)) {
        for(i = 1; i <= n; i ++) {
            cin >> a[i];
            ans[i] = a[i];
            transform(a[i].begin(), a[i].end(), a[i].begin(), ::tolower);
        }
        cin >> instr;
        transform(instr.begin(), instr.end(), instr.begin(), ::tolower);
        s = (char *) instr.c_str();
        ac.init();
        ac.insert(ac.root, s, false);
        for(i = 1; i <= n; i ++) {
            if(ac.run((char *) a[i].c_str())) {
                cout << i << " " << ans[i] << endl;
            }
        }
    }
    return 0;
}



	//字典树一发入魂！
//楼上的 悟空 是我的小伙伴哦O(∩_∩)O~ 

#include<iostream>
#include<string>
using namespace std;
struct node {
	int line;
	string data;
}Arr[1010];

void toLow(string &str) {
	for (int i = 0; i < str.size(); i++) {
		if (str[i] <= 'Z' && str[i] >= 'A') {
			str[i] += ('a' - 'A');
		}
	}
}

bool judge(string str, string regular) {
	toLow(str);
	toLow(regular);
	int i, j;
	string tmp;
	for (i = 0,j = 0; i < str.size() && j < regular.size(); i++,j++) {
		if (str[i] == regular[j]) continue;
		// 不相等
		if (regular[j] != '[') {
			return false;
		}
		else {
			j++;
			for (; regular[j] != ']'; j++) {
				tmp += regular[j];
			}
			if (tmp.find(str[i]) == -1) {
				return false;
			}
		}
	}
	if (i != str.size() || j != regular.size()) {
		return false;
	}
	return true;
}
int main() {
	int n;
	while (cin >> n) {
		for (int i = 0; i < n; i++) {
			cin >> Arr[i].data;
			Arr[i].line = i + 1;
		}
		string regular;
		cin >> regular;
		for (int i = 0; i < n; i++) {
			if (judge(Arr[i].data, regular)) {
				cout << Arr[i].line << " " << Arr[i].data << endl;
			}
		}
	}	
	return 0;
}

//AC代码：
#include<string>
#include<iostream>
#include<vector>
#include<map>
#include<stdio.h>
using namespace std;
map<int,string> res;
bool equals(string a,string b){
    if(a.length()!=b.length()) return false;
    for(int i=0;i<a.length();i++)
        if('a'<=a[i]&&a[i]<='z'){
            int tmp=a[i]-'a';
            if((int)(b[i]-'a')!=tmp&&(int)(b[i]-'A')!=tmp)
                return false;
        }else if('A'<=a[i]&&a[i]<='Z'){
            int tmp=a[i]-'A';
            if((int)(b[i]-'a')!=tmp&&(int)(b[i]-'A')!=tmp)
                return false;
        }else{
            if(a[i]!=b[i]) return false;
        }
    return true;
}
string x;
void dfs(int index,string step,vector<string>&dict){
    if(index>=x.length()){
        for(int j=0;j<dict.size();j++)
            if(equals(step,dict[j]))
                res[j+1]=dict[j];
    }else{
        int i;
        if(x[index]!='[')
            dfs(index+1,step+x[index],dict);
        else{
            int j,k;
            for(j=index;x[j]!=']';j++);
            for(k=index+1;k<j;k++)
                dfs(j+1,step+x[k],dict);
        }
    }
}
int main(){
    int n,i,j,k;
    //freopen("input.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        vector<string> dict(n);
        for(i=0;i<n;i++) cin>>dict[i];
        cin>>x;
        res.clear();
        vector<string> m; 
        dfs(0,"",dict);
        map<int,string>::iterator it;
        for(it=res.begin();it!=res.end();it++)
            printf("%d %s\n",it->first,(it->second).c_str());
    }
}//用dfs把所有情况搜索一遍，然后在给出的dict中匹配
 //楼下还有字典树的解法哟~
 //楼下的 MyIsBoy 是我的小伙伴O(∩_∩)O~

import java.util.Scanner; import java.util.regex.Pattern; public class Main{    public static void main(String [] args){         Scanner sc=new Scanner(System.in);         int n=sc.nextInt();         String[] s=new String[n];         for(int i=0;i<n;i++)             s[i]=sc.next();         String patt=sc.next();         Pattern pattern=Pattern.compile(patt, Pattern.CASE_INSENSITIVE|Pattern.UNICODE_CASE);                  for(int i=0;i<s.length;i++){             if((pattern.matcher(s[i]))!=null){                 System.out.println(i+" "+s[i]);             }         }     } }