于是他錯誤的點名開始了

我發現有關hash得題目有些是可以通過map數組來完成的：何為map數組，我們先思考一下最簡單的桶的排序，桶排序是將我們需要數字最為下標輸進數組中，而數組是存放的數字是這個數字出現的次數，但是由于如果數據過大且數字并不稠密，則會導致浪費很多空間。而map數組也是桶排序一樣的思想，我們首先來看map數組是怎樣定義的？

map<string ,int>a;

string是字符串的意思，這個是將字符串作為下標，后面的int就是map數組所存的數字，一般運用于這個字符串出現了幾次。看看這個思路是不是和桶排序差不多。這個map在#include<map>這個頭文件中

好既然我們知道了如何使用map，那我們就壓迫思考如何使用map數組來解決這一道題目
思路如下：我們將每一個字符串作為map數組的下標，如果是第一次出現那么map的int類型就要為1。接下來進行第2次輸入字符串，如果發現這個字符串作為下標的int值為1，那么就輸出OK ，而且將這個下標記為2，如果下一次這個字符串作為下標再一次出現，且int值為2，就說明已經重復了，那么我們就輸出REPEAT.如果int是其他值就說明根本沒有出現過，那么就直接輸出WRONG

代碼如下?

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
map<string ,int>a;
string s1,s2;
int n,m;
int main()
{cin>>n;while(n--){cin>>s1;a[s1]=1;}cin>>m;while(m--){cin>>s1;if(a[s1]==1){printf("OK\n");a[s1]=2;}else if(a[s1]==2){printf("REPEAT\n");}else{printf("WRONG\n");}}return 0;
}

A-B 數對

首先我們需要轉換思路，題目讓我求A-B=C, 我們可不可以轉換為A-C=B？完全可以
為什么我們需要做這樣的轉化？? 應為在之前A-B=C這樣我們需要從一堆數據中尋找到兩個符合要求的數字，而且答案是只有一個C。但是如果我們換了一個思路,B從哪里來？是不是從數組中來？答案就是在數組里面，那你就有可能會問了，那從數組里面找答案不是更加難嗎？no no no。我們是不是可以用map數組，如果這個出現了一次就記錄加加，我們再將數組全部都減去C這個是不是就是B，那么我們將B作為map數組下標輸進去，有幾次記錄就有幾個答案。是不是很妙？我第一次看到這樣的寫法我都震驚了。

代碼如下

#include<iostream>
#include<cstring>
#include<map>
#include<string.h>
using namespace std;
typedef long long ll;
const int N=2e5+100;
map<ll,ll> a;
ll ans[N];
ll n,c;
int main()
{cin>>n>>c;for(int i=1;i<=n;i++){cin>>ans[i];a[ans[i]]++;//這個就是A-C=B中B的個數，其實就是在答案中找ans[i]-=c;//這個就是B，如果遍歷一遍整個數組，發現在map數組中有，那么map數組中有幾個，那么就出現了幾次}ll anss=0;for(int i=1;i<=n;i++){anss+=a[ans[i]];}cout<<anss<<endl;return 0;
}

【模板】字符串哈希

仔細看這題 說是不是就是找有幾個不同的字符串？那我們換個思路是不是就是看有幾個字符串是相同的，拿著不就是和第一題差不多嘛，用一個map數組，第一個類型為string 作為下標，第二個類型為int 作為map數組具體的值，如果這個字符串出現了int 類型就進行幾次加加。最后一次遍歷，將int 的值為0進行累加

代碼如下

#include<map>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
map<string ,int>a;
string s1,s2;
int n,m;
int main()
{cin>>n;int ans=0;for(int i=1;i<=n;i++){cin>>s1;if(a[s1]==0){a[s1]=1;ans++;}}cout<<ans<<endl;return 0;
}

?[USACO09OCT] Barn Echoes G

首先我看到題目并不是先想到hash的方法，我也不知道這一題用hash怎么做，反而我先想到的是用kmp算法來寫?，他題目自己說了要使用前后綴相同來寫，這很自然的就想到了。這個題目有個坑點就是它沒說那個是主串，那個是模式串，這兩個字符串都分別作為主串和模式串來一遍kmp。

還有一個坑點就是兩個模式串第一個可以是前綴，下一個是后綴。然后還可以是第二個是前綴，第一個是后綴，所以也是要使用兩遍kmp算法來保證都能充當一次前綴后綴，模式串，主串。

然后用一個變量anss來記錄最大的長度就可以過來了（嘿嘿 我的獨創思路，還有點小自豪）

#include<iostream>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdio>
using namespace std;
char s1[100];
char s2[100];
int kmp[100];
int main()
{scanf("%s",s1+1);scanf("%s",s2+1);int len1=strlen(s1+1);int len2=strlen(s2+1);int j=0;for(int i=2;i<=len2;i++){while(j>0&&s2[i]!=s2[j+1])j=kmp[j];if(s2[i]==s2[j+1])j++;kmp[i]=j;}int ans=-1;j=0;for(int i=1;i<=len1;i++){while(j>0&&s1[i]!=s2[j+1])j=kmp[j];if(s1[i]==s2[j+1])j++;ans=max(ans,j);	}	j=0;for(int i=2;i<=len1;i++){while(j>0&&s2[i]!=s2[j+1])j=kmp[j];if(s1[i]==s1[j+1])j++;kmp[i]=j;}j=0;for(int i=1;i<=len2;i++){while(j>0&&s2[i]!=s1[j+1])j=kmp[j];if(s2[i]==s1[j+1])j++;ans=max(ans,j);	}	cout<<ans<<endl;return 0;
}