题解 P4421 [COCI2017-2018#1] Lozinke

题目描述

Recently, there has been a breach of user information from the mega-popular social network Secret Network. Among the confidential information are the passwords of all users.

Mihael, a young student who has been exploring computer security lately, found the whole thing really interesting. While experimenting with the social network, he found another security breach! When you input any string of characters that contains a substring equal to the actual password, the login will be successful. For example, if the user whose password is abc inputs one of the strings abc, abcd or imaabcnema, the system will successfully log him in, whereas the login will fail for axbc.

Mihael wants to know how many ordered pairs of different users exist such that the first user, using their own password, can login as the second user.

输入输出格式

输入格式:
The first line of input contains the positive integer N (1 ≤ N ≤ 20 000), the number of users.

Each of the following N lines contains the user passwords. The passwords consist of at least one and at most 10 lowercase letters of the English alphabet.

输出格式:
The first and only line of output must contains the number of ordered pairs from the task.

输入输出样例

输入样例#1:

输出样例#1:

输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:

说明

Clarification? ?of? ?the? ?second? ?test? ?case:

The first user can login as the second user, the second user can login as the first, and the third user can login as both the first and the second user.

题目翻译

最近,社交网站Secret的用户信息遭到了入侵?网络。机密资料包括所有用户的密码。

Mihael,一个最近一直在探索计算机安全的年轻学生,发现整个事情真的很有趣。在尝试使用社交网络时,他发现了另一个安全漏洞!当您输入的字符串的任何一个子串,与实际密码相等时,登录将会成功。

例如,如果密码为abc的用户输入一个字符串abc, abcd或imaabcnema,系统会成功登入,而axbc的登入会失败。

Mihael想知道有多少对不同用户对存在这样的情况,可以让第一个用户可以使用自己的密码作为第二个用户登录。

Solution

一道水题?

下面的大神用的都是hash,本蒟蒻太弱了只会一种暴力方法,stl大法好啊。

因为读入的字符串的长度小于10,而且子串必须是连续的,这样的话子串总和并不会太多。

那么对于读入的字符串,直接暴力把这个字符串所包含的所有子集给存到set里面。

然后直接映射到map里,把子集的个数加1.

最后直接统计答案,子集为a[i](读入字符串)的有多少个。全部累加,最后需要剪掉n(因为我们把需要匹配的整个串也算进去了,要剪掉1*n个)

讲的已经很清楚了,如果不理解或者有疑问的话可以提出来,也可以私信问我。

code

发表评论