|
题目链接：点击打开链接
题目大意：
会依次给你一些串，让你判断这些串中总共有多少个单词 "doge" ,不区分大小写。
解题思路：
看到题目，很容易明白是个两串匹配。那么就要用到我们大名鼎鼎的kmp算法了。其实这本质就是一个kmp的模板题（假装沉思道）。
然而，当我看到别人做法的时候，
int main()
{
ans=0;
while(scanf(" %s",a)!=EOF)
{
int l=strlen(a);
for(int i=0;i<l;i++)
{
if((a[i]=='d'||a[i]=='D')&&(a[i+1]=='O'||a[i+1]=='o')&&(a[i+2]=='g'||a[i+2]=='G')&&(a[i+3]=='E'||a[i+3]=='e'))
ans++;
}
}
printf("%d\n",ans);
}
纳尼！！！我不信，我不信，怎么可能！！！那一瞬间，我仿佛明白了题目的含义 "Wow! Such Doge!" 。。。来自 Doge 的凝视
反正我把kmp的做法也写了，亲测除了代码变长以外没任何屁用。
啥？问我时间，自己试去，
以下为kmp代码（淦tm的kmp，妈的注释也不想打了，反正就是个模板），
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <set>
#include <functional>
#define rank ra
#define next ne
#define pb push_back
#define hash haha
#define lson rt<<1
#define rson rt<<1|1
#define xlson xl,xmid,xt<<1
#define xrson xmid+1,xr,xt<<1|1
#define ylson yl,ymid,xt,yt<<1
#define yrson ymid+1,yr,xt,yt<<1|1
using namespace std;
typedef long long ll;
char a[100005];
char s[10]={'d','o','g','e'};
int next[100005];
int ans;
void get_next(char a[])
{
int l=strlen(a);
int i=0;
int j=-1;
next[0]=-1;
while(i<l)
{
if(j==-1||a[i]==a[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
bool check(char a,char b)
{
if(a==b)
return 1;
if(b>='A'&&b<='Z'&&(b-('A'-'a')==a))
return 1;
return 0;
}
int kmp(char s[],char t[])
{
int ls=strlen(s);
int lt=strlen(t);
int j=0;
int i=0;
get_next(s);
while(i<lt&&j<ls)
{
if(j==-1||check(s[j],t[i]))
{
i++;
j++;
if(j==ls)
{
j=next[j];
ans++;
}
}
else
j=next[j];
}
if(j==ls) //匹配成功返回第一次出现的位置
return i-j;
return 0;
}
int main()
{
ans=0;
while(scanf(" %s",a)!=EOF)
{
kmp(s,a);
}
printf("%d\n",ans);
}
| 
转播
