BerOS File Suggestion
题意:
给出几个字符串,再给出几个字符串,找这些字符串在前面已给出自符串的母串有几个,输出母串个数及任意一个母串;
题解:
直接暴力,超时;每个字符串长度最大为8 ,所以把每个字符串拆成子串,用map存起来,再输入所要查找的字符串时,直接找就行。
Description
Polycarp is working on a new operating system called BerOS. He asks you to help with implementation of a file suggestion feature.
There are n
files on hard drive and their names are f1,f2,…,fn. Any file name contains between 1 and 8
characters, inclusive. All file names are unique.
The file suggestion feature handles queries, each represented by a string s
. For each query s it should count number of files containing s as a substring (i.e. some continuous segment of characters in a file name equals s
) and suggest any such file name.
For example, if file names are "read.me", "hosts", "ops", and "beros.18", and the query is "os", the number of matched files is 2
(two file names contain "os" as a substring) and suggested file name can be either "hosts" or "beros.18".
Input
The first line of the input contains integer n
(1≤n≤10000
) — the total number of files.
The following n
lines contain file names, one per line. The i-th line contains fi — the name of the i-th file. Each file name contains between 1 and 8
characters, inclusive. File names contain only lowercase Latin letters, digits and dot characters ('.'). Any sequence of valid characters can be a file name (for example, in BerOS ".", ".." and "..." are valid file names). All file names are unique.
The following line contains integer q
(1≤q≤50000
) — the total number of queries.
The following q
lines contain queries s1,s2,…,sq, one per line. Each sj has length between 1 and 8
characters, inclusive. It contains only lowercase Latin letters, digits and dot characters ('.').
Output
Print q
lines, one per query. The j-th line should contain the response on the j-th query — two values cj and tj
, where
- cj
is the number of matched files for the j
- -th query,
- tj
- is the name of any file matched by the j
- -th query. If there is no such file, print a single character '-' instead. If there are multiple matched files, print any.
Sample Input
Input
4 test contests test. .test 6 ts . st. .test contest. st
Output
1 contests 2 test. 1 test. 1 .test 0 - 4 .test
代码:
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<map>
using namespace std;
#define maxn 100010
map<string,int>str1;
map<string,string>str2;
int main()
{
int n,i,j,m;
string a,b,c;
while(scanf("%d",&n)!=EOF)
{
while(n--)
{
cin>>a;
map<string,int>outrepeat;
for(i=0;i<a.size();i++)
{
for(j=1;j<=a.size();j++)
{
b=a.substr(i,j);
cout<<b<<endl;
if(outrepeat[b]==0)
{
str1[b]++;
str2[b]=a;
outrepeat[b]=1;
}
}
}
}
cin>>m;
while(m--)
{
cin>>c;
if(str1[c]>0)
cout<<str1[c]<<" "<<str2[c]<<endl;
else
cout<<"0 -"<<endl;
}
}
return 0;
}
上一篇: c语言中形参和实参有什么区别
推荐阅读
-
Could not load file or assembly 'Microsoft.SqlServer
-
Oracle数据备份过程中遇BUG_ORA-27054 NFS file system
-
jQuery中:file选择器用法实例教程
-
Apache启动错误Permission denied: httpd: could not open error log file解决方法
-
PHP file_exists问题杂谈_php技巧
-
PHP file_exists问题杂谈
-
jquery-file-upload 的php mysql插入有关问题
-
PHP中fopen,file_get_contents,curl函数的区别,curlgetcontents
-
javascript - JQuery 如何传递input file的内容至PHP进行处理
-
如何能知道XML对象中有几个一层的元素 simplexml_load_file()