[hdu4763]next数组的应用

http://acm.hdu.edu.cn/showproblem.php?pid=4763

题目大意:给一个字符串,判断是否可以写成ABACA,B、C表示长度大于等于0的字符串。

方法:ans = next[len]如果小于等于len/3,则ans是最大可能的答案,否则ans = next[ans] 要继续往前走,直到ans <= len/3, 然后枚举从2*ans位置枚举到len - ans,看是否存在某个位置j, 使得next[j] = ans,当然这里也有一个往前走的过程(如果next[j]一开始大于ans),具体见代码:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <map>
 7 #include <vector>
 8 #include <stack>
 9 #include <string>
10 #include <ctime>
11 #include <queue>
12 #define mem0(a) memset(a, 0, sizeof(a))
13 #define mem(a, b) memset(a, b, sizeof(a))
14 #define lson l, m, rt << 1
15 #define rson m + 1, r, rt << 1 | 1
16 #define eps 0.0000001
17 #define lowbit(x) ((x) & -(x))
18 #define memc(a, b) memcpy(a, b, sizeof(b))
19 #define x_x(a) ((a) * (a))
20 #define LL long long
21 #define DB double
22 #define pi 3.14159265359
23 #define MD 10000007
24 #define INF (int)1e9
25 #define max(a, b) ((a) > (b)? (a) : (b))
26 using namespace std;
27 char str[1200000];
28 int next[1200000];
29 void getNext()
30 {
31         next[0] = next[1] = 0;
32         for(int i = 1; str[i]; i++) {
33                 int j = next[i];
34                 while(j && str[i] != str[j]) j = next[j];
35                 next[i + 1] = str[i] == str[j]? j + 1 : 0;
36         }
37 }
38 int solve()
39 {
40         int len = strlen(str), ans = next[len], F = 0;
41         while(ans * 3 > len) ans = next[ans];
42         while(ans) {
43                 for(int i = ans * 2; i <= len - ans; i++) {
44                         int j = next[i];
45                         while(j > ans) j = next[j];
46                         if(j == ans) {
47                                 F = 1;
48                                 break;
49                         }
50                 }
51                 if(F) break;
52                 ans = next[ans];
53         }
54         return ans;
55 }
56 int main()
57 {
58         //freopen("input.txt", "r", stdin);
59         int T;
60         cin>> T;
61         for(int i = 1; i <= T; i++) {
62                 scanf("%s", str);
63                 getNext();
64                 cout<< solve()<< endl;
65         }
66         return 0;
67 }

时间: 11-11

[hdu4763]next数组的应用的相关文章

hdu4763(KMP的应用)

题意:给一个字符串,问最长的一个子串A,他是前缀,同时是后缀,并且中间也出现过A.并且出现的三个A都不没有重叠部分. 解法:先KMP求出失配数组,然后将所有的是后缀且是前缀的打上标记,然后遍历整个next数组,(对于每个位置的next来说,一直next向前取就是找到此前缀的一个个是整个字符串前缀的后缀,比较绕)暴力枚举判断每个串的所有匹配前缀的后缀是否合法. 代码: /**************************************************** * author:xi

HDU4763 Theme Section 【KMP】

Theme Section Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1114    Accepted Submission(s): 579 Problem Description It's time for music! A lot of popular musicians are invited to join us in t

移除数组中第一个负数后的所有负数

scala> val a = ArrayBuffer[Int](1, 2,3, 5, -1, 2, -3, -5) a: scala.collection.mutable.ArrayBuffer[Int]= ArrayBuffer(1, 2, 3, 5, -1, 2, -3 , -5)   scala> :paste // Entering paste mode (ctrl-D tofinish)   var foundFirstNegative = false val keepIndexes

NumPy基础:数组和失量计算

NumPy : Numerical Python,是高性能科学计算和数据分析的基础包. 部分功能: ndarray:一个具有矢量算术运算和复杂广播能力的快速且节省空间的多维数组: 用于对整组数据进行快速运算的标准数学函数(无需编写循环): 用于读写磁盘数据的工具以及用于操作内存映射文件的工具: 线性代数.随机数生成以及傅里叶变换功能: 用于集成C.C++.Fortran等语言编写的代码工具: 大部分数据分析应用关注的功能: 用于

Matlab - 求数组的零值与过零点索引

function zeroindex=pickzero(x)%找出数组的零值及过零点(正负相交处,可能偏离0)m = length(x);x1=x(1:m-1);x2=x(2:m);indz = find(x==0); %zero pointindzer = find(x1.*x2<0); %negative/positiven=length(indzer);for i=1:n if abs(x(indzer(i)))>abs(x(indzer(i)+1)) indzer(i)=indzer(

Java中数组的概念

1.什么是二维数组?有几种表达方式?分别是什么? 答:多维数组即数组的数组,即数组的元素也是数组. 例:int[] [] a = {{1},{1,2},{1,2,3}}; 有三种方式 1).int [] [] a;  2).int [] a1 [];  3).int a2 [] []; *强烈推荐用第1种,不容易混淆a的数据类型: 2.多维数组的创建过程是什么? 答: 例:int [] [] a = new int [2] []; a[0] = {1,2,3}; a[1] = {4,5,6};

ES6之主要知识点(六)数组

引自http://es6.ruanyifeng.com/#docs/array 1.扩展运算符(...) 扩展运算符(spread)是三个点(...).它好比 rest 参数的逆运算,将一个数组转为用逗号分隔的参数序列. 该运算符主要用于函数调用. function push(array, ...items) { array.push(...items); } function add(x, y) { return x + y; } var numbers = [4, 38]; add(...n

数组、字符串、集合

数组与集合的转换.数组与字符串的转换 ========数组变集合 String[] arr = {"abc","cc","kkkk"}; //把数组变成list集合有什么好处? /* 可以使用集合的思想和方法来操作数组中的元素. 注意:将数组变成集合,不可以使用集合的增删方法. 因为数组的长度是固定. contains. get indexOf() subList(); 如果你增删.那么会产生UnsupportedOperationExcepti

c#数组的count()和length的区别

C# 数组中 Length 表示数组项的个数,是个属性. 而 Count() 也是表示项的个数,是个方法,它的值和 Length 一样.但实际上严格地说 Count() 不是数组的内容,而是 IEnumerable 的内容.这也是为什么 C# 2.0 时数组不能用 Count(),而 3.0 后就可以用 Count() 的原因. 对于数组,据说用 Length 快于 Count(). 所以一般情况:数组我用 Length,IEnumerable(比如 List)我用 Count().