返回信息流2、有一篇英文文章(也就是说每个单词之间由空格分隔)，请找出“csdn”着个单词出现的次数，要求效率最高，并写出算法的时间级。
网上有人给了解题思路，硬是没有看出来名堂。。。
解题思路：
第二个问题，其实很简单。
假设不区分大小写，由于英文字母有26个，因此，可以将单词映射为数字。csdn被映射成:
( 'c '- 'a ')*32*32*32+( 's '- 'a ')*32*32+( 'd '- 'a ')*32+( 'n '- 'a ')
即：( 'c '- 'a ')*(1 < <15)+( 's '- 'a ')*(1 < <10)+( 'd '- 'a ')*(1 < <5)+( 'n '- 'a ')
求高人解读，指点。。。3X
这是一条镜像帖。来源：北邮人论坛 / cpp / #26084同步于 2009/7/10
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
请教个小算法题。
camelBUPT
2009/7/10镜像同步10 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
kmp预处理是klogk(k是模式串长度, n是母串长度), 比较O(n)
此算法预处理 O(1), 比较O(n), 两个算法几本差不多, 只是此算法预处理比较快
这个算法充分利用了内建类型比较的高效，但是局限性也很明显，一旦模式串过长(超过6个字符),无法用一个int表示,这个算法也就歇菜了
#include <iostream>
#include <cstring>
int map(char c)
{
return c - 'a';
}
int find_csdn(char * src, int len)
{
if (len < 4) return 0;
int ans = 0;
int csdn = (map('c') << 15) + (map('s') << 10) + (map('d') << 5) + map('n');
int tmp = (map(src[0]) << 10) + (map(src[1]) << 5) + map(src[2]);
for (int i=3; i<len; i++)
{
tmp = ((tmp << 5) + map(src[i]))%(1 << 20); // 这里是关键
if (tmp == csdn) ans++;
}
return ans;
}
int main()
{
char txt[] = "csdn csdnndsdsdn csdn";
std::cout << find_csdn(txt, strlen(txt)) << std::endl;
}
单词固定的情况下拿个自动机扫一遍，写起来还更方便些
【 在 wolf5x 的大作中提到: 】
: 说的是HASH吧，对一个单词，用5bit保存每个字母，这样把单词转成数字。
: 不过这样得先把全文都转成数字存？
: 好像还不如直接kmp...
看到大家讨论的，手痒痒了，试写了个，对算法的复杂度怎么度量一直不是很清楚，这个的复杂度是O(n)么？
#include <iostream>
#include <cstring>
int find_csdn(char a[],int len)
{
int count=0;
int temp=0;
for(int i=0;i<len;i++)
{
if(a[i]=='c')
{
temp=1;
}
else if(a[i]=='s')
{
temp=(temp<<1)&2;
}
else if(a[i]=='d')
{
temp=(temp<<1)&4;
}
else if(a[i]=='n')
{
temp=(temp<<1)&8;
if(temp!=0)
count++;
}
}
return count;
}
int main()
{
char txt[] = "csdn csdnndsdsdn csdn";
std::cout << find_csdn(txt, strlen(txt)) << std::endl;
return 0;
}
【 在 lvwenlong 的大作中提到: 】
: 看到大家讨论的，手痒痒了，试写了个，对算法的复杂度怎么度量一直不是很清楚，这个的复杂度是O(n)么？
: #include <iostream>
: #include <cstring>
: ...................
这个复杂度是O(n), 但有个常数比较大,因为有个if分支