spoj untitled

untitled是叉姐认为的最麻烦的字符串题目之一……——主席


被虐哭了……我不会说我对这题根本没有头绪……

题意:

考虑一个序列S1与另一个序列S2,如果满足下列条件,则两个序列等价即

1、 两个序列长度相等。

2、 设序列长度为len,对于任意的i,j(1<=i,j<=Len,i!=j),若s1[i] s1[j],则s2[i]>s2[j]。

现给出序列S和另外n个序列T1,T2,…Tn。

位置i可行,当且仅当S[1..i]的某个后缀等价于T1…Tn中的某个序列。

你需要输出所有可行i的值,按照升序输出。

题解

……先来考虑怎么快速判断两个串是否相等……
离散化?可是这是不能推广到kmp或ac自动机的……
比如两个串离散化后……为1 2 3 4和2 1 3 4
1 2 3 4 和2 1 3 4显然不等
但是它们的后缀2 3 4和1 3 4是相等的TAT
考虑用什么方法描述串可以快速判断两个串相等……同时易于推广……
因为这里有用的只有大小关系
所以对于一个串,它的第i个位置的字符换成 区间[1,...,i-1]有多少字符大小 小于它
1 2 3 4->0 1 2 3
2 1 3 4->0 0 2 3
同样……如果两个串相等……当且仅当在这种表示方法下,两个串相等……
但是这样也好像不能快速判断后缀是否相等?
先看看我们是怎么求出表示的……
用树状数组求出区间[1,...,i-1]有多少字符大小 小于它……
我们可以移动左界……来得到区间[2,..,i-1]有多少字符大小小于它……
这有什么用?
我们有KMP!
KMP的fail数组(或者叫NEXT数组?不同人叫法不一样T_T)本质就是对于第i个位置找到一个最大的j,使得前缀[1,..j] === 前缀[1,..,i]的一个后缀[i-j+1,i]……
我们看看这种表示方法能不能在KMP上用到 ……
答案是肯定的……
只要得到第i个位置的fail[]我们就能利用树状数组移动左界来得到下一个位置的fail!
那么对于弱化问题:只有一个模式串的时候找出匹配的位置就可以轻松用KMP在O(nlgn)的时间内完成了

考虑原问题:

KMP做不了多串那么我们就上Ac自动机……Ac自动机的做法非常类似……但是会复杂很多……
注意这题的恶心的地方在于每个模式串都要一个树状数组……如果不想清楚的话……会弄不清维护哪一个树状数组
其次Ac自动机也是有一个小问题的……
就是字符集非常大……左儿子右兄弟会TLE……直接保存指针数组会MLE
所以我们用字符串hash来存状态!

code: https://gist.github.com/foreseeable/fb9ea6c6ca45fa6652e0

Comments

comments powered by Disqus