//AC自动机+KMP
//给定一个1000*1000的矩阵，再给定一个500*500的矩阵 问这个小矩阵是否为这个大矩阵的子矩阵
//本菜不会那些高级的搜索和hash，想了一个很挫的，但是能够保证复杂度下限的算法
//首先把小矩阵每行变成一个串，然后对这n2个串构建自动机，这个复杂度为n2*n2
//然后我们在每个位置记录下第一次出现终止位置时的下标id，这个值等价于hash了这个小矩阵的字串
//我们把大矩阵也拆成n1个字符串，对应着去跑一下这个自动机，记录下每次匹配的位置和id
//于是我们得到了一个新的矩阵c[i][j]，

#include<iostream>
using namespace std;
//后缀数组
//题目描述：求一个字符串的最长连续子串的长度。具体

#include<iostream>
using namespace std;
//AC自动机+DP
//题目描述：目标密码长为n，m为单词数当前，k为密

#include<iostream>
using namespace std;
//首先这题确实很BT，yayamao大牛神奇的20分钟秒确实很orz，lcc的40分钟秒也很orz
//这题分为这么几个步骤
//问题(1)求得fib[a^b]%c的循环节，这里我开了dp[1000][1000]hash，暴力找出循环节 这样可以得到A[0]
//问题(2)获得A序列后，队序列整体+1求后缀，获得height数组
//问题(3)将模型转化，等价于求在height数组里面找最大的矩形，对于一种字串的解，我们总可以用若干个后缀代替
//他们的公共前缀就是这个字串，而这些后缀体现在height数组中必

#include<iostream>
using namespace std;
const int maxn=30005;
//AC自动机
//给定若干病毒串，是否存在一个无线长的安全串，构建自动机，dfs这棵trie树，找环即可
int indange;
typedef struct node
{
    node *fail;
    node *next[2];
    int flag,cnt;
    void init(){flag=cnt=0;memset(next,0,sizeof(next));fail=NULL;}  
    }node;
node num[maxn*2

http://acm.pku.edu.cn/JudgeOnline/problem?id=1509

#include<iostream>
#include<cstring>
using namespace std;
//最小表示法 寻找最小字典序循环串起始位置
inline int min(int x,int y){return x<y?x:y;}
int minishow(char *s)
{
    int i,j,k,n=strlen(s);
    i=0;j=1;k=0;
    while(i<n/2&&j<n/2&&k<n/2)

题目大意，给定一个数列，第一项比其他任何项都要大，要求分成三份，不能为空，分成三份后，再翻转，求最小的序列 题中给出了最小的定义

咋一看完全没有想法，手算了下样例，猜测第一个切点很可能与最小后缀有关，后来想想这其实是贪心的一部，由于涉及翻转，先将整个字符串倒序输入，求一次后缀，然后找出最小的那个，注意要保持能分成三份，显然第一个切点必定是最小的那个点的sa值，为什么呢，这样在最大项之前，我们可以保证前面的是所有情况中字典序最小的，安顿好了最大的项及其前面最小的字典序，我们再来看第二个