hihocoder Browser Caching（字符串hash）

题目链接：点击打开链接

题意描述：

在浏览网页的时候，缓存技术能够迅速地显示页面。这里我们对浏览器的缓存技术进行简化：我们认为浏览器的缓存大小为M，表示缓存可以存储M个页面。

当用户访问URL时，浏览器会先到缓存中查询是否有该页面的记录，如果有则直接从缓存中提取数据；否则，会发送网络请求，从Internet获取该页面，并将该页面放入缓存中。当缓存中的页面数量超过M时，缓存技术会替换掉缓存中最不频繁访问的网页，即最后访问时间最早的页面。

现在，我们希望对于给定的用户访问历史记录，请判断出每一次访问页面是从缓存中读取的，还是通过网络请求获得的。(缓存最开始数据为空)

解题思路：字符串hash

分析：根据题意我们可以使用链表模拟缓存，但在判断字符串相等上如果直接判断耗时严重，所以我们可以使用字符串hash加速

代码：

#include <iostream>
#include <cstring>
#include <list>
#define MAXN 500010
#define MOD 500009
using namespace std;
int n,m;
int head[MAXN];
struct node{
    int hh;
    char* str;
    node(int _hh,char* _str):hh(_hh),str(_str){}
};
list<node> ls;
int BKDRHash(char* str){
    int seed=31;
    int ans=0;
    int len=strlen(str);
    for(int i=0;i<len;++i){
        ans=(ans*seed)+str[i];
        ans%=MOD;
    }
    return ans;
}
bool inserthash(char* str){
    int ans=BKDRHash(str);
    if(!head[ans]){
        head[ans]++;
        ls.push_back(node(ans,str));
        int len=ls.size();
        if(len>m){
            head[ls.begin()->hh]--;
            ls.pop_front();
        }
        return true;
    }
    else{
        list<node>::iterator it;
        for(it=ls.begin();it!=ls.end();++it){
            if(it->hh==ans&&strcmp(str,it->str)==0){
                ls.erase(it);
                ls.push_back(node(ans,str));
                return false;
            }
        }
        ls.push_back(node(ans,str));
        head[ans]++;
        int len=ls.size();
        if(len>m){
            head[ls.begin()->hh]--;
            ls.pop_front();
        }
        return true;
    }
}
char st[20010][100];
int main()
{
    scanf("%d%d",&n,&m);
    memset(head,0,sizeof(head));
    ls.clear();
    for(int i=1;i<=n;++i){
        scanf("%s",st[i]);
        if(inserthash(st[i])) printf("Internet
");
        else printf("Cache
");
    }
    return 0;
}