1.hash表（哈希表）
codevs 2147 数星星--简单哈希
小明是一名天文爱好者，他喜欢晚上看星星。这天，他从淘宝上买下来了一个高级望远镜。他十分开心，于是他晚上去操场上看星星。
不同的星星发出不同的光，他的望远镜可以计算出观测到的星星发出的光的数值W。小明当然想尽可能地多看到星星，于是他每看到一颗星星，就要看看他之前有没有看过这颗星星。但是他看的星星太多了，他根本数不过来，于是他让你帮忙。
共有两行，第一行只有一个整数，为小明观测到的星星的数量n。第二行有n个整数，每两个整数由一个空格隔开，分别为小明观测到每颗星星的光的数值W[1]-W[n]。
只有一行，这一行共有n个数字0或1。0表示对应的星星之前没有观测到，1表示对应的星星之前已经看过了。注意：数字之间没有空格！
5
1 5 5 4 1
00101
样例是往往是骗人的，本题中
30%的数据，0<n≤5000。
20%的数据，-20000≤W≤20000。
60%的数据，0<n≤50000。
100%的数据，0<n≤500000；-2000000000≤W≤2000000000。
分类标签 Tags 点此展开
#include<iostream> using namespace std; #define mod 500009/*取>500000的最小质数即可*/ #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> long long hash_table[mod*2]; int n,w[mod]; int main() {memset(hash_table,-128,sizeof(hash_table));scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&w[i]);int k=abs(w[i])%mod;bool flag=false;while(hash_table[k]>=-2000000000)/*you shu le*/{if(hash_table[k]==w[i])flag=true;k++;}hash_table[k]=w[i];if(flag)printf("1");else printf("0");}return 0; }
2.KMP算法[POJ3461]乌力波
法国作家乔治·佩雷克(Georges Perec，1936-1982)曾经写过一本书，《敏感字母》（La disparition），全篇没有一个字母‘e’。他是乌力波小组（Oulipo Group）的一员。下面是他书中的一段话：
Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais…
佩雷克很可能在下面的比赛中得到高分（当然，也有可能是低分）。在这个比赛中，人们被要求针对一个主题写出甚至是意味深长的文章，并且让一个给定的“单词”出现次数尽量少。我们的任务是给评委会编写一个程序来数单词出现了几次，用以得出参赛者最终的排名。参赛者经常会写一长串废话，例如500000个连续的‘T’。并且他们不用空格。
因此我们想要尽快找到一个单词出现的频数，即一个给定的字符串在文章中出现了几次。更加正式地，给出字母表{'A','B','C',...,'Z'}和两个仅有字母表中字母组成的有限字符串：单词W和文章T，找到W在T中出现的次数。这里“出现”意味着W中所有的连续字符都必须对应T中的连续字符。T中出现的两个W可能会部分重叠。
【输入格式】
输入包含多组数据。
输入文件的第一行有一个整数，代表数据组数。接下来是这些数据，以如下格式给出：
第一行是单词W，一个由{'A','B','C',...,'Z'}中字母组成的字符串，保证1<=|W|<=10000（|W|代表字符串W的长度）
第二行是文章T，一个由{'A','B','C',...,'Z'}中字母组成的字符串，保证|W|<=|T|<=1000000。
【输出格式】
对每组数据输出一行一个整数，即W在T中出现的次数。
【样例输入】
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
样例输出
1
3
0
#include<iostream> using namespace std; #include<cstdio> #include<cstring> #define MT 1000100 #define MW 10100 char w[MW],t[MT]; int ans=0; int fail[MW]; void input() {memset(w,0,sizeof(w));memset(t,0,sizeof(t));memset(fail,0,sizeof(fail));scanf("%s%s",w,t); } void make_fail() {int k=0;int lenw=strlen(w);fail[0]=0;// for(int i=1;i<=lenw;++i)// {while(k>0&&w[i]!=w[k])k=fail[k-1];// if(w[i]==w[k])k++;fail[i]=k;} } void kmp() {int lent=strlen(t);//mu int lenw=strlen(w);int k=0;for(int i=0;i<=lent;++i){while(k>0&&t[i]!=w[k])k=fail[k-1];// if(t[i]==w[k]){k++;}if(k==lenw){ans++;k=fail[k-1];}} } int main() {int t1;scanf("%d",&t1);while(t1--){input();make_fail();ans=0;kmp();printf("%d\n",ans);}return 0; }
3.【AC自动机】
BZOJ 3172: [Tjoi2013]单词
Description
某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
Input
第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6
Output
输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。
Sample Input
a
aa
aaa
Sample Output
3
1
#include<iostream> using namespace std; #define N 1000100/*最长字符串的长度*/ #include<cstring> #include<cstdio> int topt=0,n; struct Trie{int nxt[26],cnt,fail;Trie(){memset(nxt,0,sizeof(nxt));cnt=fail=0;/*结构体初始化*/} }trie[N]; int pos[201],que[N],head=-1,tail=-1; void build_trie(int k,char*str)/*建trie书的过程*/ {int now=0;while(*str){if(!trie[now].nxt[*str-'a'])trie[now].nxt[*str-'a']=++topt;now=trie[now].nxt[*str-'a'];str++;trie[now].cnt++;/*记录该前缀出现的次数*/}pos[k]=now;/*记录第k个单词终点的节点编号*/ } void input() {scanf("%d",&n);for(int i=1;i<=n;++i){char s[N];scanf("%s",s);build_trie(i,s);} } void make_fail()/*生成fail数组*/ {int now=0;trie[now].fail=0;for(int i=0;i<26;++i)/*根节点及第一层点的入队处理*/{if(!trie[now].nxt[i]) continue;que[++tail]=trie[now].nxt[i];trie[trie[now].nxt[i]].fail=0;}int p;while(head<tail){++head;now=que[head];for(int i=0;i<26;++i){if(!trie[now].nxt[i]) continue;que[++tail]=trie[now].nxt[i];/*如果存在，就入队*/p=trie[now].fail;/*p是该节点父亲的fail指针*/while(!trie[p].nxt[i]&&p)/*回调的过程*/p=trie[p].fail;if(trie[p].nxt[i])trie[trie[now].nxt[i]].fail=trie[p].nxt[i];else trie[trie[now].nxt[i]].fail=0;}}for(int i=tail;i>=0;--i)trie[trie[que[i]].fail].cnt+=trie[que[i]].cnt/*关键：从队列的反方向，因为是广搜，所以反方向的1<--3<--5都有该单词的cnt，只有反向才能把cnt一层层传上来，因为fail不一定会指向我们想要的位置*/;for(int i=1;i<=n;++i)printf("%d\n",trie[pos[i]].cnt);/*这是该单词的这终结点，但是也许别的单词中也会包括该单词，因为这是广搜，所以包含该单词的单词终结位置的fail一定指向当前这个单词，上面那一步就是，把这里的单词数转移上去*/ } int main() {input();make_fail();return 0; }
4.【manacher算法--回文串】
| Time Limit: 15000MS | Memory Limit: 65536K | |
| Total Submissions: 6831 | Accepted: 2534 |
Description
A string is said to be a palindrome if it reads the same both forwards and backwards, for example "madam" is a palindrome while "acm" is not.
The students recognized that this is a classical problem but couldn't come up with a solution better than iterating over all substrings and checking whether they are palindrome or not, obviously this algorithm is not efficient at all, after a while Andy raised his hand and said "Okay, I've a better algorithm" and before he starts to explain his idea he stopped for a moment and then said "Well, I've an even better algorithm!".
If you think you know Andy's final solution then prove it! Given a string of at most 1000000 characters find and print the length of the largest palindrome inside this string.
Input
Output
Sample Input
abcbabcbabcba abacacbaaaab END
Sample Output
Case 1: 13 Case 2: 6
题目大意：求最长回文子串的长度
#define L 1000100 #include<iostream> using namespace std; #include<cstdio> #include<cstring> using namespace std; char s[L*2+100]; int p[L*2+100],id; int lens; int ans=-1; void input() {lens=strlen(s);for(int i=lens;i>=0;--i){s[i+i+2]=s[i];/*预处理加#，偶数是原字母，奇数和0是#*/s[i+i+1]='#';}s[0]='#'; } void manacher() {ans=0;id=0;p[id]=0;for(int i=1;i<=lens*2+2;++i)/*别忘了跑2*lens+2才可以*/{if(id+p[id]>i)p[i]=min(p[2*id-i],id+p[id]-i);while(s[i+p[i]]==s[i-p[i]])p[i]++;if(i+p[i]>id+p[id])id=i;ans=max(ans,p[i]);} } int main() {int topt=0;while(scanf("%s",s)==1){++topt;if(strcmp(s,"END")==0) break;input();manacher();printf("Case %d: %d\n",topt,ans-1);/*ans-1是因为添加了#*/memset(s,0,sizeof(s));/*不要忘记初始化*/memset(p,0,sizeof(p));}return 0; }