2.9 learning summary

Today, let's solve the Haas algorithm problem . It is also the template problem of this algorithm Just a little bit about my understanding .

The title is as follows .

  A classic template question .  The core of the algorithm is the basic application of hash algorithm . Through the hash algorithm . To make a unique hash value for each string . To distinguish strings . This is a template .  That is, the difference in order is solved by multiplying each time by a number .  Because for this continuous mathematical formula .  The order affects the size of the results .  For the number of digits, it means that each operation is performed or a value set randomly by oneself is added .  Then you can implement this algorithm . Of course, this is not entirely accurate .

 ans=(ans*base+(f)s[i])%m+p;

That's the formula above .

To make a long story short , The hash algorithm used for the string , It is also a very simple reason for this algorithm .  But make their hash values as small as possible , Not equal . The complete code is as follows ,

 #include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef long long f;
f base=123;
f a[100000];
char s[100000];
int n,ans=1;
f m=12345678987654;
f p=555;
f hashe(char s[])
{
 int len=strlen(s);
 f ans=0;
 for (int i=0;i<len;i++)
 ans=(ans*base+(f)s[i])%m+p;
 return ans;
}
int main()
{
 scanf("%d",&n);
 for(int i=0;i<n;i++)
 {
 	scanf("%s",s);
 	a[i]=hashe(s);
 }
 sort(a,a+n);
 for(int i=0;i<n-1;i++)
 {
 	if(a[i]!=a[i+1])
 	ans++;
 }
 printf("%d",ans);
 return 0;
} 

Then let's talk about another problem I wrote .

The title is as follows .

  I used a function that I hadn't touched before , Namely map function .  For external functions , I think that is to establish a mapping relationship . Or say map The function creates a free array .  For arrays , The mapping relationship is implemented by the following symbols . in other words a[i]=? But for map Come on . This i  Will no longer be numbers   It is Custom data types ,

So for the above topic , We just need to use one map  function , It can be solved by using the idea of bucket row . Specifically, mark all given names first .  Then, when the second set of data is given, it is traversed .  If it has been marked, it will be output ,ok.  Output without tag wrong, Then for each output ok After the operation of , Then mark it . Cover it with . After traversing the data for the second time . It outputs repeat.  The specific code is as follows ,

#include<map>
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
map<string,int>a;  
char s[10000000];
int n,m;
int main(){
    scanf("%d",&n);
    while(n--){ 
    	cin>>s;
    	a[s]=1; 
    }
   scanf("%d",&m);
    while(m--){
    	cin>>s;
    	if(a[s]==1){
			printf("OK\n");
		a[s]=2;}
    	else if(a[s]==2){
		printf("REPEAT\n"); }
    	else printf("WRONG\n");
    }
	return 0;
}

*** .