Codeforces Round 764 (Div. 3) -- E. Masha-forgetful

**
题目大意：取去模板串中的子串可以组成一个给定的目标串，每个子串可以用无数次， 输出组成的所需的串的信息

题目中的取得子串必须 “>= 2” 很好的提示了我们， 想到一个式子 2 * x + 3 * y 可以等于任何数， 所以从之前的串都取长度为2， 为3。
在进行匹配。
**

struct node {
	int l, r, idx;
};

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> f(m + 1, 0);
    map<string, node> mp;
    for (int i = 1; i <= n; i ++)
    {
    	string s;
    	cin >> s;
    	// cout << s << '\n';
    	for (int j = 0; j < s.size(); j ++)
    	{
    		string s1 = "";
    		for (int k = 0; k + j < s.size() && k < 3; k ++)
    		{
    			s1 += s[k + j];
    		}
    		if (s1.size() == 3) mp[s1] = {j + 1, j + 3, i};
    		s1 = "";
    		for (int k = 0; k + j < s.size() && k < 2; k ++)
    		{
    			s1 += s[k + j];
    		}
    		if (s1.size() == 2) mp[s1] = {j + 1, j + 2, i};
    	}
    }
    // for (auto t : mp) cout << t.first << ' ';
    // cout << '\n';
    string s;
    cin >> s;
    s = ' ' + s;
    f[0] = 1;
    for (int i = 1; i < s.size(); i ++)
    {
    	if (i >= 2)
    	{
    		string s1 = "";
    		for (int j = 1; j >= 0; j --)
    			s1 += s[i - j];
    		// cout << s1 << '\n';
    		if (mp.count(s1) && s1.size() == 2) f[i] += f[i - 2];
    	}
    	if (i >= 3)
    	{
    		string s1 = "";
    		for (int j = 2; j >= 0; j --)
    			s1 += s[i - j];
    		
    		if (mp.count(s1) && s1.size() == 3) f[i] += f[i - 3];
    	}
    }
    if (f[s.size() - 1] == 0) {cout << -1 << '\n'; return;}
    int idx = m;
    vector<node> ans;
    while (f[idx])
    {
    	if (idx == 0) break;
    	if (idx - 2 >= 0 && f[idx - 2] != 0)
    	{
    		string s1 = "";
    		for (int i = idx - 1; i <= idx; i ++)
    		{
    			s1 += s[i];
    		}
    		ans.push_back({mp[s1].l, mp[s1].r, mp[s1].idx});
    		idx -= 2;
    		continue;
    	}
    	if (idx - 3 >= 0 && f[idx - 3] != 0)
    	{
    		string s1 = "";
    		for (int i = idx - 2; i <= idx; i ++)
    		{
    			s1 += s[i];
    		}
    		ans.push_back({mp[s1].l, mp[s1].r, mp[s1].idx});
    		idx -= 3;
    		continue; 
    	}
    }
    cout << ans.size() << '\n';
    for (int i = ans.size() - 1; i >= 0; i --)
    {
    	cout << ans[i].l << ' ' << ans[i].r << ' ' << ans[i].idx << '\n';
    }
}