Hashing

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H(key)=key%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions. Note that the table size is better to be prime.
If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.

Input Specification

Each input file contains one test case. For each case, the first line contains two positive numbers: MSize(104)MSize (≤10^4) and N(MSize)N (≤MSize) which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.

Output Specification

For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print “-” instead.

参考代码(转)

#include<iostream>
#include<cmath>
#define MSIZE 10050
using namespace std;
int msize,n,num,htable[MSIZE];
void insert(int);
bool isprime(int);
int main(){
cin>>msize>>n;
while(!isprime(msize))msize++;
for(int i=0;i<n;i++){
    cin>>num;
    insert(num);
    if(i<n-1)cout<<' ';
}
cout<<endl;
}
bool isprime(int m){
int i;
if(m==1)return false;
for(i=sqrt(m);i>1;i--)if(!(m%i))return false;
return true;
}
void insert(int key){
for(int d=0;d<msize;d++){
    int pos=(key+d*d)%msize;
    if(!htable[pos]){
        htable[pos]=key;
        cout<<pos;
        return;
    }
}
cout<<'-';
} 

Hashing - Hard Version

Given a hash table of size N, we can define a hash function H(x)=x%N. Suppose that the linear probing is used to solve collisions, we can easily obtain the status of the hash table with a given sequence of input numbers. However, now you are asked to solve the reversed problem: reconstruct the input sequence from the given status of the hash table. Whenever there are multiple choices, the smallest number is always taken.

Input Specification

Each input file contains one test case. For each test case, the first line contains a positive integer N(1000)N (≤1000), which is the size of the hash table. The next line contains N integers, separated by a space. A negative integer represents an empty cell in the hash table. It is guaranteed that all the non-negative integers are distinct in the table.

Output Specification

For each test case, print a line that contains the input sequence, with the numbers separated by a space. Notice that there must be no extra space at the end of each line.

Sample Input

11
33 1 13 12 34 38 27 22 32 -1 21

Sample Output

1 13 12 21 33 34 38 27 22 32

分析

  • 已知H(x)=x%N以及用线性探测解决冲突问题
  • 先给出散列映射的结果,反求输入顺序
    • 当元素x被映射到H(x)位置,发现这个位置已经有y了,则y一定是在x之前被输入的
    • ————————>拓扑排序!!!

ac代码

#include<iostream>
#include<cstdlib>
#include<stack>
#define range 1050
using namespace std;
int n,num,htable[range],temp[range],output[range],myhash(int),cmp(const void*,const void*);
stack<int>s1,s2;
void insert(int),hashing();
bool find(int);
int main(){
    cin>>n;
    int i,j;
    for(i=0,j=0;i<n;i++){
        cin>>num;
        htable[i]=num;
        if(num>0)output[j++]=num;
    }
    qsort(output,j,sizeof(int),cmp);
    for(i=j-1;i>=0;i--)s1.push(output[i]);
    hashing();
}
int cmp(const void*num1,const void*num2){
    return *(int*)num1-*(int*)num2;
}
int myhash(int key){
    return key%n;
}
bool find(int key){
    int pos=myhash(key);
    while(temp[pos]&&temp[pos]!=key)++pos%=n;
    if(key==htable[pos]){
        temp[pos]=key;
        return true;
    }
    return false;
}
void hashing(){
    int i=0;
    while(!s1.empty()){
        while(!find(s1.top()))s2.push(s1.top()),s1.pop();
        output[i++]=s1.top(),s1.pop();
        while(!s2.empty())s1.push(s2.top()),s2.pop();
    }
    for(int j=0;j<i-1;j++)cout<<output[j]<<' ';
    cout<<output[i-1]<<endl;
}

KMP 串的模式匹配

给定两个由英文字母组成的字符串String和Pattern,要求找到Pattern在String中第一次出现的位置,并将此位置后的String的子串输出。如果找不到,则输出“Not Found”。
本题旨在测试各种不同的匹配算法在各种数据情况下的表现。各组测试数据特点如下:
数据0:小规模字符串,测试基本正确性;
数据1:随机数据,String长度为10510^5,Pattern长度为1010
数据2:随机数据,String长度为10510^5,Pattern长度为10210^2
数据3:随机数据,String长度为10510^5,Pattern长度为10310^3
数据4:随机数据,String长度为10510^5,Pattern长度为10410^4
数据5:String长度为10610^6,Pattern长度为10510^5;测试尾字符不匹配的情形;
数据6:String长度为10610^6,Pattern长度为10510^5;测试首字符不匹配的情形。

输入格式

输入第一行给出 String,为由英文字母组成的、长度不超过10^6的字符串。第二行给出一个正整数N(10)N(≤10),为待匹配的模式串的个数。随后N行,每行给出一个Pattern,为由英文字母组成的、长度不超过10510^5的字符串。每个字符串都非空,以回车结束。

输出格式

对每个Pattern,按照题面要求输出匹配结果。

输入样例

abcabcabcabcacabxy
3
abcabcacab
cabcabcd
abcabcabcabcacabxyz

输出样例

abcabcacabxy
Not Found
Not Found

ac代码

#include<iostream>
#include<string>
#define range 100500
using namespace std;
int n,mynext[range];
string str,ptn;
void kmp(string),match(string);
int main(){
    cin>>str>>n;
    for(int i=0;i<n;i++){
        cin>>ptn;
        kmp(ptn);
    }
}
void kmp(string ptn){
    int s=0,p=0,lens=str.size(),lenp=ptn.size();
    match(ptn);
    while(s<lens&&p<lenp){
        if(str[s]==ptn[p])s++,p++;
        else if(p>0)p=mynext[p-1]+1;
        else s++;
    }
    if(lenp==p)cout<<str.substr(s-p)<<endl;
    else cout<<"Not Found"<<endl;
}
void match(string ptn){
    mynext[0]=-1
    for(int i=1;i<ptn.size();i++){
        int j=mynext[i-1];
        while(j>=0&&ptn[i]!=ptn[j+1])j=mynext[j];
        if(ptn[i]==ptn[j+1])mynext[i]=j+1;
        else mynext[i]=-1;
    }
}