字符串乱搞&Tricks

0.省流版

• 字符集是26个小写字母，Trie的循环里面不要写异或，写减号
• map >可能比bitset快

1.字符串hash

to be continued...

2.KMP

to be continued...

3.Manacher

to be continued...

4.ExKMP

to be continued...

5.Trie

• 用map套静态数组卡空间

应用:P3879 阅读理解

这题出出来就是为了卡空间的
一开始用vector存了以每个点为结尾的串所属文章号
然后就\(\tt \color{purple}{MLE}\)了
去搜了下，发现map不仅可以套vector还可以套静态数组array
它的声明是:

array < Typename , Size > Array_Name

然后用它存了bool来判断每篇文章是否有这个串
一开始看错了数据范围，定义了一个10001大小的，发现还是MLE，遂康康TJ换成了bitset<10001> mp[MAXN]，结果它直接\(\tt \color{yellow}{CE}\)了？？？
然后才发现dev本地编译时，map可以过而bitset不能过
然后才发现我范围开错了……
吔，等等
那map怎么过了（
所以就成功地发现了这个东西的nb之处（

上边的是bitset，下边的是map套array
可以发现，这样套出来竟然比bitset这种极致压缩的结构占空间还要小！

虽然不懂原理，而且我觉得这样写的空间其实跟数据有关
但是以后如果bitset写锅了，或者毒瘤人卡了空间
可以试试map套静态数组.
另外，bitset还是比map要快的（

code:

#include 
#define ri register int
#define MAXN 5000001
#define g() getchar()
#define pc(a) putchar(a)
#define Tp template
using namespace std;

namespace SlowIO
{
	Tp inline void rd(T &x)	{
		x=0;char i=g();bool f=1;
		while(!isdigit(i)) f&=(i!='-'),i=g();
		while(isdigit(i)) x=(x<<3)+(x<<1)+(i^48),i=g();
		x*=((f<<1)-1);
		}
	Tp inline void op(T x){
		if(x<0) pc('-'),x=-x;
		if(x>=10) op(x/10);
		pc(x%10+48);
		}
	Tp inline void writeln(T x){op(x);pc('\n');}
	Tp inline void writesp(T x){op(x);pc(' ');}
	Tp inline void writespf(T x){pc(' ');op(x);}
};
using namespace SlowIO;

int trie[MAXN][26];
int n,m,tot;
map > mp;
string s;

void insert(int ind){
    ri ptr=0,len=s.length();
    for(ri i=0;i>s,insert(i);
    } rd(m);
    while(m--){
        cin>>s;
        getans(); pc('\n');
    }
    return 0;
}