HDU 5510 Bazinga 字符串HASH (2015ACM/ICPC亚洲区沈阳站)

2024-08-27 02:08

本文主要是介绍HDU 5510 Bazinga 字符串HASH (2015ACM/ICPC亚洲区沈阳站),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目链接】:click here~~

【题目大意】:

Bazinga

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 39    Accepted Submission(s): 15


Problem Description
Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.

For  n  given strings  S1,S2,,Sn , labelled from  1  to  n , you should find the largest  i (1in)  such that there exists an integer  j (1j<i)  and  Sj  is not a substring of  Si .

A substring of a string  Si  is another string that occurs  in  Si . For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".

Input
The first line contains an integer  t (1t50)  which is the number of test cases.
For each test case, the first line is the positive integer  n (1n500)  and in the following  n  lines list are the strings  S1,S2,,Sn .
All strings are given in lower-case letters and strings are no longer than  2000  letters.

Output
For each test case, output the largest label you get. If it does not exist, output  1 .

Sample Input
  
4 5 ab abc zabc abcd zabcd 4 you lovinyou aboutlovinyou allaboutlovinyou 5 de def abcd abcde abcdef 3 a ba ccc

Sample Output
  
Case #1: 4 Case #2: -1 Case #3: 4 Case #4: 3

求前i个字符串不是该i字符串的子串的最大的i值

【思路】暴力KMP,暴力字符串HASH

此处留坑代填~~

先放挫挫代码:

/*
* Problem: HDU No.5510
* Running time: 399MS
* Complier: G++
* Author: javaherongwei
* Create Time: 17:30 2015/10/31 星期六
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef unsigned long long LLU;
const LLU base=1e9+7;
const int N=505;
const int M=2020;
char s[N][M];
LLU f[N][M], fac[M];
vector<int> val;
int n, len[N];
LLU get(int i, int l, int r)
{return f[i][r]-f[i][l-1]*fac[r-l+1];
}
bool check(int x, int y)
{if(len[y]>len[x]) return false;for(int i = len[y]; i <= len[x]; i++){if(f[y][len[y]] == get(x,i-len[y]+1,i)) return true;}return false;
}
int solve()
{for(int i = 0; i < n; i++){len[i] = strlen(s[i]+1);f[i][0] = 0;for(int j = 1; j <= len[i]; j++){f[i][j] = f[i][j-1]*base+s[i][j]-'a'+1;}}int ans = -1;val.clear();val.push_back(0);for(int i = 1; i < n; i++){while(val.size()){if(check(i, val[val.size()-1])){val.pop_back();}else  break;}val.push_back(i);if(val.size()>1) ans = i+1;}return ans;
}
void init()
{fac[0] = 1;for(int i = 1; i <= 2002; i++) fac[i] = fac[i-1]*base;
}
int main()
{//freopen("1.txt","r",stdin);init();int t, tot = 0;scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%s", s[i]+1);printf("Case #%d: %d\n", ++tot, solve());}return 0;
}



这篇关于HDU 5510 Bazinga 字符串HASH (2015ACM/ICPC亚洲区沈阳站)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1110328

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

python中Hash使用场景分析

《python中Hash使用场景分析》Python的hash()函数用于获取对象哈希值,常用于字典和集合,不可变类型可哈希,可变类型不可,常见算法包括除法、乘法、平方取中和随机数哈希,各有优缺点,需根... 目录python中的 Hash除法哈希算法乘法哈希算法平方取中法随机数哈希算法小结在Python中,

Springboot3+将ID转为JSON字符串的详细配置方案

《Springboot3+将ID转为JSON字符串的详细配置方案》:本文主要介绍纯后端实现Long/BigIntegerID转为JSON字符串的详细配置方案,s基于SpringBoot3+和Spr... 目录1. 添加依赖2. 全局 Jackson 配置3. 精准控制(可选)4. OpenAPI (Spri

使用Python实现base64字符串与图片互转的详细步骤

《使用Python实现base64字符串与图片互转的详细步骤》要将一个Base64编码的字符串转换为图片文件并保存下来,可以使用Python的base64模块来实现,这一过程包括解码Base64字符串... 目录1. 图片编码为 Base64 字符串2. Base64 字符串解码为图片文件3. 示例使用注意

golang float和科学计数法转字符串的实现方式

《golangfloat和科学计数法转字符串的实现方式》:本文主要介绍golangfloat和科学计数法转字符串的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望... 目录golang float和科学计数法转字符串需要对float转字符串做处理总结golang float

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length):从右侧截取指定长度的字符SUBST

Python将字符串转换为小写字母的几种常用方法

《Python将字符串转换为小写字母的几种常用方法》:本文主要介绍Python中将字符串大写字母转小写的四种方法:lower()方法简洁高效,手动ASCII转换灵活可控,str.translate... 目录一、使用内置方法 lower()(最简单)二、手动遍历 + ASCII 码转换三、使用 str.tr