学步园

今天AMAZON的一道题，其实数据很弱，直接暴力都能过的。

然后第一反应是用字典树，就是如果匹配到*号的时候，就把一层都往下搜索一遍。

然后第二反应是用KMP，这样复杂度是O(n * (n+m ) )的。

直接字符串读取一行还没弄出来。囧。

#include<iostream>
#include<vector>
#include<string>
#include<cstdio>
using namespace std;

bool isMatch(char a,char b)
{
	if(a=='*'||b=='*')
		return true;
	return tolower(a)==tolower(b);
}

void initP(const string& s,vector<int>& pre)
{
	pre[0]=-1;
	for(int i=1;i<s.size();i++)
	{
		int p=pre[i-1];
		while(p!=-1&&isMatch(s[p+1],s[i]))
			p=pre[p];
		if(isMatch(s[p+1],s[i]))
			pre[i]=p+1;
		else
			pre[i]=-1;
	}
}
bool kmp(const string& s,const string& t,int& start)
{
	vector<int> pre(t.size(),-1);
	initP(t,pre);
	int pt=-1;
	int len=s.size();
	for(int ps=-1;ps<len;ps++)
	{
		while(pt!=-1&&!isMatch(s[ps+1],t[pt+1]))
			pt=pre[pt];
		if(isMatch(s[ps+1],t[pt+1]))
		{
			pt++;
			if(pt==t.size()-1)
			{
				start=ps-t.size()+2;
				return true;
			}
		}
	}
	return false;
}
int getMatchCount(vector< string > patterns, string input) {
	
	int n= input.size();
	int ans=0;
	vector<vector<int> > match(n,vector<int>(n,0));
	for(int i=0;i<patterns.size();i++)
	{
		int start=0;
		if(kmp(input,patterns[i],start))
		{
			if(match[start][start+patterns[i].size()-1]==0)
			{
				match[start][start+patterns[i].size()-1]=1;
				ans++;
			}
		}
	}
	return ans;
}
int main()
{
	int n;
	while(cin>>n)
	{
		vector<string> pats(n);
		for(int i=0;i<n;i++)
			cin>>pats[i];

		
		string input("this is a word for pattern matching");
		int ans=getMatchCount(pats,input);
		cout << ans<<endl;
	}
}