KMP字符串匹配

进行多次KMP字符串匹配即可

#include <iostream>
#include <cstring>
#include <vector> 
using namespace std;

vector<int> build_next(string b)
{
	vector<int> next(b.size(), 0);
	int k = 0;
	for (int i = 1; i < b.size(); i++)
	{
		while(k > 0 && b[i] != b[k])
		{
			k = next[k-1];
		}
		
		if (b[i] == b[k])
		{
			k++;
		}
		
		next[i] = k;
	}
	return next;
}

bool KMP(string a, string b)
{
	if (b.size() <= 0)
	{
		return 0;
	}
	int k;
	int count = 0;
	vector<int> next = build_next(b);
	for (int i = 0; i < a.size(); i++)
	{
		while(k > 0 && a[i] != b[k])
		{
			k = next[k-1];
		}
		
		if (a[i] == b[k])
		{
			k++;
		}
		
		if (k == b.size())
		{
			return false;
		}
	}
	return true;
}

int main()
{
	int n;
	cin >> n;
	bool flag = true;
	vector<string> tests(n, "");
	
	for (int i = 0; i < n; i++)
	{
		cin >> tests[i];
	} 
	
	string str;
	cin >> str;
	
	for (int i = 0; i < n; i++)
	{
		flag = flag && KMP(str, tests[i]);
	}
	
	if (flag)
	{
		cout << "true" << endl;
	}
	else
	{
		cout << "***" << endl;
	}
	return 0;
}