0%

串的朴素模式匹配

较简单,略过。

KMP算法(朴素模式匹配的优化)

朴素模式匹配的缺点是:每当模式串匹配失败的时候,当前的匹配指针都只是往后移动一位,也就是只是把模式串右移一位,而且主串的扫描指针(模式串中匹配到哪一位)都要经常回溯,会造成多余的开销。

假定在某个主串中要匹配google这个模式串,那么其匹配逻辑如下:

  • 声明主串扫描指针为i;
  • 声明模式串扫描指针为j;
  • KMP的算法关键在于匹配失败时,j回溯,而i不回溯(下标从0开始)。
  • 当j>0匹配成功时,j++,i++
  • 当j=0匹配不成功时,j不变,i++
  • 当j>0匹配不成功时,j回到最后一个有可能接下来匹配成功的下标,i不变(比如模式串google,在j等于4时不匹配,那么j应该回溯到1)

j指针的具体回溯如下,并且可以一个int类型数组来存储器其回溯的下标。

  • 若当前两个字符匹配,则i++,j++
  • 若j=0时发生不匹配,则应让i++,但是此时的next[j]=-1
  • 若j=1时发生不匹配,则应让j回到0
  • 若j=2时发生不匹配,则应让j回到0
  • 若j=3时发生不匹配,则应让j回到0
  • 若j=4时发生不匹配,则应让j回到1
  • 若j=5时发生不匹配,则应让j回到0

数组next[0]=-1 next[1]=0 next[2]=0 next[3]=0 next[4]=1 next[5]=0

BOILERPLATE:

Read more »

单词结尾的s什么时候读 “s” 与 “z”

  • 做动词时结尾读”z”
  • 做形容词、副词、名词时结尾读”s”







参考来源知乎

字母组合发音

ar

1
/ɑː/

garbage

Read more »

Yesterday I had a phone call from Clint. I was very surprised. I ______ (write) to him many times but he ______ (never, reply) to my letters.
答案:had written, had never replied
解析:两个或两个以上相继发生的动作,用and或but按动作发生的先后顺序连接,此时要用一般过去时,而不用过去完成时。过去完成时则强调主语在过去的某一时刻“回顾”更早的动作。具体来说,如果在谈论过去某一事件时,又想到在这之前已发生的某事,就要用过去完成时态。

A: I need to find a dermatologist.(皮肤科医生) You’re familiar with Dr. Smith. Do you recommend her?
B: Well, I ______ (see) by her a few times. And the best I can say for her is she has interesting magazines in her waiting room.
答案:have been seen
解析:在英语中,“动作表达”的完成时态强调最近发生的事件,而“状态表达”的完成时态强调“较远的过去”经历。

It’s reported that by the end of this month the output of cement in the factory ______ (rise) by about 10%.
答案:will have risen
解析:将来完成时是以“将来”作为“坐标时间”,来表示开始于将来之前(可能是过去、现在或将来)的动作持续到将来。但动作开始的时间并不重要,关键是说话人要站在将来的某一时间来谈某一动作的完成情况。

I have entered the university for two years.
答案:错误,应改为:I have been in the university for two years,或者用一般过去时态说成:I entered the university two years ago.

He has left his native place for three years.
答案:“单一事件”完成时的肯定句不与持续的时间状语连用,动词leave(left的原形)是非延续性动词,不能跟一段时间状语(否定句除外)。

A: Are you glad you came to China?
B: Yes. Indeed. 我本来是要考虑去Tokyo or Singapore, but 我从不后 悔我的决定。
答案:I’d considered going to Tokyo or Singapore, but I’ve never regretted my decision.
解析:表示“非真实”的过去,主要是指intend,mean,hope,want,plan,suppose,expect, think,propose和wish等动词用于过去完成时,可表示过去未能实现的计划、设想、意图或希望等。

George would certainly have attended the proceedings ______.
A. had he not had a flat tire
B. had the tire no flattened itself
C. if the flat tire hadn’t happened
D. if he didn’t get a flat tire
答案:A

If Greek civilization ______ all of Europe, English wouldn’t contain so many Greek words.
A. hadn’t influenced
B. doesn’t influence
C. hasn’t influenced
D. didn’t influence
答案:A

Nelson ______ the fight, with a little more training and a better manager.
A. would win
B. had won
C. could have won
D. won
答案:C
解析:尼尔森本可以赢得这场战斗,但需要更多的训练和更好的教练。

He would rather ______ than worked last night.
A. have slept
B. has slept
C. sleep
D. slept
答案:A
解析:本题考查 would rather have done 的虚拟句型,本题相当于“He would rather have slept than have worked last night.” ,后边的 have 被省去了。

Read more »

语法

标记

1
2
3
4
5
6
**这是加粗的文字**
*这是倾斜的文字*`
***这是斜体加粗的文字***
~~这是加删除线的文字~~
>这是引用的内容
==背景高亮==

分割线

1
2
3
4
---
----
***
*****

图片

1
![图片alt](图片地址 ''图片title'')

超链接

1
[超链接名](超链接地址 "超链接title")

列表

Read more »