14426 접두사 찾기 [미완]

으음 입력이 10000이라 n^2일테니 그냥 이중포운 돌리자! 싶었는데 접두사 비교하는 부분이 문제였다.

 

그래서 미리 접두사를 다 만들어놓으면 어떨까 싶었음. 

 

이걸 미리 만들어두고 비교하는 방식으로 하면 되겠다 싶었는데 미리 만들어 둔 거 길이가 5000000 이만큼이어서 NlogN으로 했을 때 터져버리는 것 같다.. 으음... 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int     main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int n, m;
	cin >> n >> m;

	string s;
	vector<string> v;
	for (int i = 0; i < n; i++)
	{
		cin >> s;

		string sub = "";
		for (int j = 0; j < s.size() ; j++)
		{
			sub += s[j];
			//cout << sub << "\n";
			v.push_back(sub);
		}
	}

	sort(all(v));

	int cnt = 0;
	for (int i = 0; i < m; i++)
	{
		string s;

		cin >> s;
		auto a = lower_bound(all(v), s);
		if (*a == s)
			cnt++;
	}

	cout << cnt;

	return 0;
}