WordsInteresting

There are multiple test cases. The first line of the input contains an integer N, indicating the number of test cases. For each test case:
The first line contains a string S and an integer n (1 ≤ |S| ≤ $10^5$ , 1 ≤ n ≤ 20), indicating the Interesting Word and the number of the Source Words, |S| indicating the length of the string.
In the following n lines, each line contains a string T (1 ≤ |T| ≤ $10^5$ ), indicating the following Source Words, |T| indicating the length of each string.
It's guaranteed that the string can only be made up by the lowercase letters, and the sum of the length of the string |S| and |T| of all test cases will not exceed 2× $10^6$ .

Java(javac 1.8) 解法, 执行用时: 287ms, 内存消耗: 30964K, 提交时间: 2020-09-18 16:10:32

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner s=new Scanner(System.in);
		int t=s.nextInt();
		while(t-->0)
		{
			String a=s.next();
			int x=s.nextInt();
			int b[][]=new int[2][26];
			for(int i=0;i<a.length();i++)
			{
				b[0][a.charAt(i)-'a']++;
			}
			boolean panduan=true;
			while(x-->0)
			{
				String c=s.next();
				if(!panduan){continue;}
				int wz=0;
				for(int i=0;i<c.length();i++)
				{
					b[1][c.charAt(i)-'a']++;
					while(wz<a.length()&&a.charAt(wz)!=c.charAt(i))
					{
						wz++;
					}
					wz++;
					if(wz>a.length())
					{
						System.out.println("No");
						panduan=false;
						break;
					}
				}
			}
			if(panduan)
			{
				boolean p=true;
				for(int i=0;i<26;i++)
				{
					if(b[1][i]<b[0][i])
					{
						System.out.println("No");
						p=false;
						break;
					}
				}
				if(p)
				{
					System.out.println("Yes");
				}
			}
		}
		
	}

}

C++14(g++5.4) 解法, 执行用时: 87ms, 内存消耗: 1760K, 提交时间: 2020-09-18 15:05:40

#include<bits/stdc++.h>
using namespace std;
string s[25];
int slen[25];
int a[27];
int b[27];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string str;
		int n;
		cin>>str>>n;
		memset(slen,0,sizeof(slen));
		for(int i=0;i<26;i++)
		{
			a[i]=b[i]=0;
		}
		for(int i=0;i<n;i++)
		{
			cin>>s[i];
		}
		int len=str.length();
		for(int i=0;i<len;i++)
		{
			a[str[i]-'a']++;
			for(int j=0;j<n;j++)
			{
				if(str[i]==s[j][slen[j]])
				{
					slen[j]++;
					b[str[i]-'a']++;
				}
			}
		}
		int flag=0;
		for(int i=0;i<n;i++)
		{
			if(slen[i]!=s[i].length())
			{
				flag=1;
				break;
			}
		}
		for(int i=0;i<26;i++)
		{
			if(a[i]>b[i])
			{
				flag=1;
				break;
			}
		}
		if(!flag)cout<<"Yes\n";
		else cout<<"No\n";
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 26ms, 内存消耗: 1508K, 提交时间: 2020-06-06 14:55:06

#include<cstdio>
#include<cstring>
char s[100005],c[25][100005];
int count[30];
int main(){
	int i,j,k,n,len,len0,t,flag;
	while(scanf("%d",&t)!=EOF){
		scanf("%s %d",s,&n);
		for(i=0;i<n;i++){
			scanf("%s",c[i]);
		}
		flag=1;
		memset(count,0,sizeof(count));
		len=strlen(s);
		for(i=0;i<len;i++){
			count[s[i]-'a']++;
		}
		for(i=0;i<n;i++){
			len0=strlen(c[i]);
			for(j=0,k=0;j<len0;j++){
				while(c[i][j]!=s[k]&&k<len) k++;
				if(c[i][j]==s[k]){
					count[s[k]-'a']--;
				}
				else if(k>=len){
					flag=0;break;
				}
			}
			if(flag==0) break;
		}
		for(i=0;i<26;i++){
			if(count[i]>0){
				flag=0;break;
			}
		}
		if(flag==0) printf("No\n");
		else printf("Yes\n");
	}
	return 0;
}

详情