Tuckman’s Group Development

Tuckman’s model a.k.a. Tuckman ladder is one of the most widely-used models to describe group development which consists of five development phases that teams may go through. PMBOK claims the importance of team building to project success shown below.

Teamwork is a critical factor for project success, and developing effective project teams is one of the primary responsibilities of the project manager.

PMBOK Guide, P337

With respect to the Agile way of working, team building is the only way to achieving self-organisation and delivering the highest possible value. Hence, the model provides a reliable way for project managers, ScrumMasters, Agile Coaches and other roles to help identify the current stage of teams, so as to adopt different approaches and techniques for team building more efficiently and effectively.

Tuckman’s Model in PMP and Scrum

The significant characteristics of the team presenting during each phase of Tuckman’s model have been categorised into PMP and Scrum respectively (collected from PMBOK Guide and “The Great ScrumMaster”). It should be noticed that the characteristics shown in the column of PMP would also be identified in Scrum teams in real practice, while the opposite would be not due to the circumstances under the specific framework (Scrum). Also, in each phase, the works ScrumMasters should focus on have been listed as well.

In 1977, the fifth phase was added: adjourning, that involves completing the task and breaking up the team (in some texts referred to as “mourning”).

In the IT area, most teams have improved during the entire project lifecycle, and the team environment and collaboration among team members would have reached higher levels. However, the project is a temporary endeavour, it is inevitable that staff would be released after the project is completed. PRINCE2 also mentioned the necessitate to reduce this loss. This is a quite interesting topic.

When a project has involved high levels of collaboration and teamwork, and the team is disbanded, it can result in a degree of ‘mourning‘ for the team members, so this should be anticipated and ideas suggested as to how reduce this.

PRINCE2 Agile Manual, P 194

Norming vs. Performing

As for the model, the most puzzled part for me is how to differentiate the phases of Norming and Performing. These are both the comfortable stages for teams, which show high performance and productivity. So let’s have a look of the relationship between team effectiveness and team performance during each phase.

In short, the team in the Norming phase is not bad, but not good enough. The team should still be encouraged to take ownership and responsibility and continue improving, so as to become self-organisation.

Should the ScrumMaster be responsible for removing impediments?

This is one of the questions I was asked most frequently during the interviews these days. And my original answer to this question was OBVIOUSLY NO! In order to make the answer convincing, let’s find out some evidence to support it.

Scrum Guide

The ScrumMaster role is deemed as a servant leader in Scrum Guide. And there are a number of specific responsibilities of the ScrumMaster listed when the ScrumMaster collaborates with the Product Owner, the dev team and the organisation respectively. With regard to “removing impediments”, there is only one point shown as:

Removing impediments to the Development Team’s progress.

However, Scrum Guide also claims that the dev teams are empowered and self-organised, which means “no one (not even the Scrum Master)” can take responsibilities of understanding, scheduling, implementing the work of the dev teams except themselves. And a dev team’s work is to deliver potentially releasable increments during each Sprint to meet Sprint Goal and to accomplish the Scrum team’s goal. Consequently, It seems that the dev teams should remove impediments emerging from the progress of delivering potentially releasable increments themselves.

CSM Course

Then I checked the material of the CSM course I attended. There is a clearer definition of the ScrumMaster role as follow:

Product Owner is responsible for the “What”, ScrumMaster for facilitating the “How”.

So the ScrumMaster is the facilitator to the dev team who is responsible for the “How”. And one of the works of the ScrumMaster is to “remove impediments on behalf of the team”. My tutor explained sometimes impediments may come from outside the team. As a coordinator between the team and the outside, the ScrumMaster is more capable of handling the interaction between the team and the outside to ensure the team focuses on the goal and creates maximum value. “Essential Scrum” supports this point of view as well,

The ScrumMaster is also responsible for protecting the team from outside interference and takes a leadership role in removing impediments that inhibit team productivity (when the individuals themselves cannot reasonably resolve them).

“Essential Scrum” P16

“The Great ScrumMaster”

This book introduces the pathway to become a great ScrumMaster with the goal of encouraging self-organisation. As mentioned in About “The Great ScrumMaster”, ScrumMasters focus on build Agile culture from the team level to the organisation level. Hence, the author defines several models relevant to the ScrumMaster role, the Scrum Team and the organisation based on the Agile maturity respectively, such as #ScrumMasterWay, Tuckman’s Group Development, Shu Ha Ri, etc. At the initialling stage of all of these models, the author suggests the ScrumMaster should help the team understand and follow the rules of Scrum rigorously, in the meanwhile, remove the impediments identified during the day to day work if necessary. Because at the beginning of Agile transformation, creating a sense of Agile inside the group is the most important and urgent task for the whole team/organisation. And the members need to be taught and facilitated rather than coach due to the lack of the sense of self-organisation. But the ultimate responsibility of the ScrumMaster is to help the team remove impediments themselves as opposed to being an administrative position of the team. Anyway, the way of how to help the team deal with impediments depends on the level of Agile maturity and self-organisation of the team in real practice.

Discussing With My Friend

I supposed that it is necessary to judge whether the ScrumMaster needs to actively resolve the problem according to its importance and urgency, which can be assessed by The Eisenhower Matrix. The reason is whether using Agile or waterfall, the ultimate goal of the teams is to achieve the goals of the project or organisation. If there is a very serious problem that may affect the product to be released, whoever finds it must immediately point it out. But if the impediment would not damage to short-term goals, such as low efficiency of the dev team due to internal communication problems, then it is necessary for the ScrumMaster to help them identify the impediment, think about solutions and iteratively adapt themselves.

Last week I have discussed this question with one of my friend Esone who has been working as a ScrumMaster for a couple of years. This point of view owns his support greatly. And he also indicates one of the advantages of doing this way that I have never recognised before. He found that if the ScrumMaster finds and points out an important and urgent technical problem in actual work, team members would be more likely to respect and accept the ScrumMaster, so as to collaborate with the ScrumMaster proactively.

Summary

In conclusion, I would say this question should be discussed and answered in several situations.

  1. The ScrumMaster should determine the current stage of the team. If the team is at the beginning of Agile transformation with less self-organisation, help the team identify, think and resolve impediments in an Agile way of working.
  2. The ScrumMaster should identify the cause of the impediment. If the impediment is caused by the outside of the team, the ScrumMaster needs to solve it through communication and coordination with external to ensure that the team can focus on achieving the goals.
  3. The ScrumMaster should assess the importance and urgency of impediments toward the goals of the team and organisation. If there is a big threat, say it and address it as fast as possible.
  4. Otherwise, help the team remove impediments themselves so as to encouraging self-organisation.

Finally, do not forget the team should analyse root causes, inspect and adapt together during the retrospective meetings no matter where the team is and no matter what kind of impediments occurs.

About “The Great ScrumMaster”

“The Great ScrumMaster” was recommended to me during an Agile workshop I attended several weeks ago. The book is not thick which mainly introduces how to become a great ScrumMaster through building a self-organised team. As Linda Rising suggests in the foreword of this book, “this is a guidebook along the path, the way, for ScrumMasters and Agile coaches“. However, I reckon that it is not only applicable to the people who work as ScrumMasters but also to the entire Scrum team.

There are three parts of the content of this book I have divided into roughly as follows: the ScrumMaster role, team building and the toolbox including useful methods, models and techniques that can be employed to help the team become better. From the ScrumMaster’s point of view, “The Great ScrumMaster” interprets the responsibilities of this role explicitly which are all around team building. And it provides various relevant models and methods for ScrumMasters to analyse, plan and implement. The reason why this book could be applicable to all members of the Scrum team is that it can help members to understand the purpose of applying Scrum, clarify the goals of the team, and identify the current situations accordingly, so as to collaborate with the ScrumMaster efficiently and effectively.

At the beginning of the book, the author exposes a rather common but serious phenomenon that the ScrumMaster is usually deemed as a valueless role subconsciously. I suppose there are two situations that cause this kind of bias. First, the team does not have a deep understanding of Scrum. Second, the ScrumMaster does not help the team reveal any apparent improvements. As a result, the role of ScrumMaster becomes formalistic and bureaucratic and may even turn to be mixed with other roles. For example, there is a person who works as the ScrumMaster, in the meantime, as the Product Owner of the team. In this manner, there would be a great conflict between business needs and team self-awareness.

This brings up a quite interesting topic, whether the ScrumMaster needs to be responsible for delivery. In this book, the author states that the ScrumMaster only needs to serve the team and determines the team’s self-organization as the ultimate goal (while I have some different understandings on this point of view, and I will explain it separately in another post). However, I cannot agree more about that encouraging self-organization is the ultimate goal of the ScrumMaster. In the Agile Principles, it is mentioned that “the best architectures, requirements and designs emerge from self-organising teams“. Only if the self-organised team owns the competency to accomplish the work and meet its goals efficiently and effectively. Additionally, there is a fact that needs to be highlighted:

Every self-organised team is self-organised only inside the given boundaries.

As I mentioned in An Overview of Agile, Agile is a set of ideological values that can not only improve productivity but also contribute to a better working environment. However, we should be aware that it would be impossible for teams and organisations to become Agile without applying any rules due to the complex circumstances. In fact, the widely-used Agile frameworks, like Scrum, have been proven as the powerful approaches to contribute to Agile culture. Therefore, defining boundaries is necessary for any Agile teams or organisations in order to achieve the values of Agile. With regard to the boundaries of Scrum, Zuzi (the author of “The Great ScrumMaster“) suggests “Scrum boundaries are determined by the process – limited by Sprint Goals, Backlogs, and delivering working product at the end“.

Scrum is not a methodology – it is a pathway.

Ken Schwaber (2005)

I always believe that a great ScrumMaster can be deemed to a great parent who takes the right way to educate their kids. Normal parents only teach their children in a way that they understand or feel is correct, but great parents will guide and facilitate their children according to the different stages of the children and current deficiencies. Kids will always grow up. It is very difficult to face this world independently if they always live under the protection of their parents. This view also coincides with the author of this book.

Unless the ScrumMaster gives the team the opportunity to take over these tasks, she ends up as their ‘mother’ who is so loving and caring that her ‘kids’ are low-confidence grown-ups, dependent on her even in their thirties

So, A Great ScrumMaster should

  1. believe in Agile and Scrum.
  2. believe in people.
  3. be a servant leader.
  4. focus on observing and listening first.
  5. aim to encourage self-organisation.
  6. try to change the world to be better.

Methods for Retrospective Meetings

Retrospectives are fundamental events not only in Scrum but also in various Agile frameworks as formal meetings to inspect and adapt the way and environment Agile teams work. There are plenty of interesting and attractive methods applied to determine the structure of retrospective meetings in real practices. So in this post, some of them are gathered and simply introduced.

Blob Football

Colouring a blob person image to depict how the sprint went. Details of Blob Football can be found in The Blob Retro.

Car Brand

Choosing a specific car brand to depict how the sprint went and then choosing your dream car. Details can be found in The Car Brand Retrospective.

DAKI

DAKI helps the team identify specific features, behaviours or activities that the team members think they should Drop, Add, Keep or Improve. Details can be found in DAKI – Agile Retrospectives Exercise.

Emojis

Using various emojis to gauge how the team feels during the Sprint. Details can be found in Emoji Retrospectives 😃.

Fast & Furious

Classifying the events each member performed during the Sprint into five categories and determining the emerged improvements. Details can be found in Retrospective #5: Fast and Furious.

Jack Sparrow

Finding pictures of pirate Jack Sparrow online and using his various faces to gauge how the sprint went. Details can be found in Guest blog: Many Faces of Jack Sparrow – Agile Retrospective Exercise.

Kudo Cards

Using Kudo Cards to help deliver feedback and motivate people. Details can be found in Retrospective with Kudo Cards.

Legos

Having team members build something to represent how the sprint went. Details can be found in Agile Retrospectives with Legos.

Sail Boat

Visualising and analogising each perspective to help the team identify the conditions they met during the sprint and discuss the solutions mutually. Details can be found in The Sail Boat Retrospective.

Weather Forecast

Using a weather metaphor to shift focus from simply looking back, to how the team expect things will go based on how things have played out so far. Details can be found in Predicting The Weather: A Weather Forecast Retrospective for Scrum Teams.

Starfish

making a pie chart divided into 5 parts which looks like a starfish with a section for “start doing”, “stop doing”, “less of”, “more of”, and “keep doing”. Details can be found in Starfish retrospective and Starfish Retrospective Technique.

Thank You

Saying “Thank you” to other members via a “Thank You” certificate. Details can be found in The Thank You Retrospective.

Traffic Lights

An action-oriented retrospective style, generating an immediate list of practical ideas for continuous improvement. Details can be found in Sprint Retrospective Techniques.

3Ws

Evaluating how happy the team is about the different Scrum elements (roles, events, artifacts, principles, values, etc.). Details can be found in 40 ideas to spice up your retrospective

4Ls

A great data gathering activity for recurring retrospectives. The Ls stand for: liked,  learned, lacked, and longed for. Details can be found in 4 Ls: Liked – Learned – Lacked – Longed For.

关于《黑暗中的笑声》

很高兴又认识了一位来自俄国的伟大作家,虽然他之后去了其它国家。这是我在书荒的时候不经意时在网上了解到的大师,几乎所有人对他的评价都只剩夸赞,就像所有俄国作家都对普希金一样毫不吝啬地赞美。我很喜欢这本书的这个第二个名字,虽然在还没翻开阅读前因为这个名字让我对故事产生了误解,我本以为是一个关于即将度过黑暗时充满希望的笑声,可它却讲了一个悲剧收尾的狗血三角恋。

故事从欧比纳斯的生活开始,他是个特别有钱的人,是一个天真且无趣的富二代,在遇见玛戈(女主)他的人生就像“坐在黑洞洞的大厅里,活像一只呆鸟”。因此他希望在平淡的生活里找到一点激情,另一方面又十分依赖稳定的婚姻所带来的安全感。当他第一次与玛戈互动时就有个很有意思的描写,欧比纳斯努力偷偷脱下手上的戒指,试图隐瞒已经结婚的事实,但在脱下之后又觉得手指又轻又空,而戒指上还留着余温。

女主玛戈,在我心里是个恶魔派来勾引男人的女人,那个骗夏娃吃苹果的蛇。不过这都是靠她一步步“长大”造成的。十二岁时又一次在楼梯上从一个捡到的破手提包中看到了一块粘着卷曲的毛的香皂和几张奇怪的照片;十三岁时“着了魔似的爱看电影”,也许就是这时候从心里萌生了当电影明星都梦;十六岁时因为受到一位认识的姑娘的影响,也希望能当一名模特,首先这份工作能养活自己,其次觉得这个职业是成为电影明星的一个容易的开头,但也在这一年,她被一个骑摩托车的西班牙小伙子侵犯了;十七岁时成功成为了一名裸体模特,在工作时间里会为了解闷而勾引好看的男子,为了找点乐趣会提前化妆甚至给乳头涂上口红,但此时她有点意识到这条通往影星的路并不好走;同年她恋爱了,准确地来说其实也不算真正的恋爱,看了场歌剧,一个星期之后就睡在一起了,睡了一个月之后她的男朋友就跑了,顺便给她付了房租,因为没钱还陪了两个日本人和一个老头睡觉。与欧比纳斯相识的目的是认为他能带来金钱和关系,让她过上好的生活并且成为电影明星,但对于这个电影明星的梦想并没有在她的身上感受到强烈的渴望,反而那种天生擅于‘玩弄’男人的特质十分显眼,去欧比纳斯家中,故意将他锁在房里,频繁给他打电话,写信到他家。然而在玛戈的美色之下,这些有明显目的性的举动却得到了欧比纳斯默认的原谅,就算知道小舅子知晓也觉得“他也是男人,应该理解男人的处境”,就算因为妻子可能看到玛戈写的信而悲伤痛哭时,也会因为玛戈的吻而解除烦恼。而故事中三角恋的另一个主角,雷克斯相比之下目的显得更加单纯而又坚定,他只想要肉欲和金钱。

我最喜欢的是玛戈主演的电影首映的桥段,几乎全部角色都出现在电影院里,除了欧比纳斯可怜的妻子。当玛戈与观众们观看她出演的电影的首映时(按书中所描述的场景来看,玛戈事先并没有看过电影,这也是她第一次看到成片),对自己的表现十分不满意,甚至觉得羞愧。其实玛戈是一个有正常判断力的人,虽然一直沉溺在明星梦中,但在电影中每个片段都无时无刻将玛戈粗糙、呆板的演技展现在观众面前时,她也做出了与大家一致的判断。电影中的玛戈更接近于现实中最真实的她,或者说是未来中的她。年华就像包裹着她的一层密不透风的精致包装,可能在几年后的某一天晚上就突然降解了,没了这层包装后玛戈只剩下与她母亲及其相似的外貌和身材,这时候她那单纯到愚蠢的内心像是没了保护罩一般完全裸露在所有人面前,虽然看上去可怜,但并没有人想同情。电影一结束,玛戈就哭着跑了,她可不能忍受如此真实的自己被这么多人围观了一两个小时。

就像之前说过的我最开始的误解,让我一度认为整个故事中的每一次有关于“黑暗”的描写都有一个共同的隐喻,因此我还特地计算了一下“黑”在小说中出现的次数。虽然这个黑暗最终被男主的失明所定义,但整个故事本身展现的是从一种“黑暗”到另一种更加“黑暗”的过程。欧比纳斯那无趣的生活是黑暗的,因此他在黑暗中被玛戈的手电筒照亮。可这光给他带来了是短暂的明亮,以至于将其指引到更加黑暗的地方 – 家庭破裂,女儿夭折,倾家荡产,车祸失明,以及最终的死亡。所有人心中总有一片黑暗出现的时候,也总会有“一束光”的出现,一束“贪婪”的光的出现。那些诸如欧比纳斯的人们抵挡不住它的诱惑,即使知道光的尽头是更加恐惧的黑暗,却总幻想在下一步时自己一定能坚定地停下脚步。这让我想到爱德华兄弟小时候的错误选择,不惜触犯禁忌打开真理之门来尝试复活自己的母亲,可最终面对的是真理之门前来自神的玩笑,并付出了惨痛的代价。书中最后也提到了“代价”,欧比纳斯认为自己最终承受的痛苦来自自己犯下的那个愚蠢的错误,这就是他所要付出的代价。如果他在第一次想一枪杀了那个女孩的时候扣动扳机该多好。

Single-pattern Matching Algorithms

Scenario

In computer science, there are several string-matching algorithms used to identify a position where one or several strings(patterns) are found within a larger string or text. In this post, 4 widely-used algorithms are applied to address the problem of single-pattern matching, including Brute Force (BF) algorithm, Rabin–Karp (RK) algorithm, Boyer–Moore (BM) algorithm and Knuth–Morris–Pratt (KMP) algorithm.

Here is the specification: given a pattern P and a searchable text T, both strings, determine whether the pattern appears somewhere in the text. Let’s say the length of P is n and the length of T is m, and also assume that n < m. And k = |Σ| be the size of the alphabet.

For ease of explanation, I define

T = 'penpineappleapplepen'
P = 'plep'

where n = 4, m = 19 and k = 26.

Brute Force Algorithm

A.K.A Naive string-search algorithm, is the simplest algorithm to implement with the low efficiency. It’s just to try out every possible position that P might appear in T.

Rabin–Karp Algorithm

The RK algorithm uses a rolling hash to quickly filter out positions of the text that cannot match the pattern. And due to the condition that the positions of the text which have the same hash value as the pattern but may not actually match the pattern, if the hash value equals the hash value of the pattern, it performs a full comparison at that position to make sure completely matched.

As we can see, the hash function, which converts every string into a numeric value, play a key role in the process of applying the RK algorithm. There is a popular and effective rolling hash function called the Rabin fingerprint. But we do not discuss a specific hash function here because the selection of hash functions depends on the situation of the problem to be addressed. The general implementation of the RK algorithm is shown as follows.

1. computing the hash value for the substring s[i..i+m-1]of T and the pattern P;

The trick can be used with a hash roller. A rolling hash is a hash function designed specifically to allow the operation. This formulation of the rolling hash will determine the next hash value in constant time from the previous value.

s[i..i+m-1] = s[i-1..i+m-2] - s[i-1] + s[i+m-1]

2. comparing the hash value h[i] with the hash value of P;

3. filtering out positions of the text that cannot match the pattern, and then checks for a match at the remaining positions. 

Boyer–Moore Algorithm

The BM algorithm is efficient that is the standard benchmark for practical string-search literature. The key features of the algorithm are to match the pattern from right to left, and to skip the text in jumps of multiple characters instead of searching every single character in the text. The actual shifting offset is the maximum of the shifts calculated by two shift rules. Let’s take a look of them respectively first.

The Bad Character Rule

Assume c is the character of T at the position i, so T[i] = c. Upon mismatch as c:

  • if P does not contain c, shift P entirely past i (shift by i+1). e.g. T[2] = 'n', and P does not contain 'n', then shift P to right by 3 positions.
  • otherwise, shift P to align the last occurrence (the most right) of c in P with T[i]. e.g. T[6] = 'e', and P contains 'e', then shift P to align the most right of 'e' in P with T[6].

If we grab the bad character and match it in the pattern sequentially, this will be relatively inefficient and will affect the performance of this algorithm. Hence, it’s time to introduce the Boyer–Moore–Horspool algorithm or Horspool’s algorithm, which is an algorithm for finding substrings in strings. An array A[] with a length of 256 (i.e., bytes) can be produced to contain each symbol in the alphabet.

First, filling A[j] with length(P), where A[j] is not contained in P.

Then, filling A[j] with length(P) - j - 1, where A[j] is contained in P (if there are more than one character same as A[j], then j equals to the position of the last occurrence one).

The Good Suffix Rule

Only applying the bad character rule cannot handle the situation such as

T = 'a'^n 
P = 'b''a'^(m-1)

Thus, a good suffix rule needs to be considered together. There is the key idea of the good suffix rule as follows.

Upon a mismatch, shift so that the already matched suffix of P aligns with a previous occurrence of that suffix (or part of it) in P.

Crucial Ingredient:
the longest suffix of P[j+1..m-1] that occurs earlier in P.

COMP526 Unit 4-4 2020-03-03 String Matching: Boyer-Moore

Two situations can be identified as:

  1. complete suffix occurs in P and the characters left of the suffix are not known to match. In order to interpret clearly, P is redefined as 'appnapp'. In this case, 'e' in T does not match 'n' in P so that 'app' is the good suffix of P. Then, we can find that the complete suffix 'app' occurs once in the characters left of the suffix in P. Consequently, we shift P to align them. If there are more than one positions matching the complete suffix, choose the most right one.

2. part of suffix occurs at the beginning of P. Well, P needs to be redefined again, let’s say P equals to 'ppnapp'. The certain suffix 'app' in P can be identified, and it does not occur anywhere else in P. However, a certain prefix 'pp' of P aligns the part of suffix 'app'. Hence, we shift P to align them. If there are more than one parts of the suffix matching the prefix, choose the most right one’s position to align.

An array B[] with the same length of P is employed to store shift if the match failed, which means for 0 <= j < m, B[j] stores shift if the match failed at P[j]. In this point, T[i+j+1..i+m-1] = P[j+1..m-1], while T[i] != P[j].

B[j] should be set as m-1-k, where k is the largest number so as to

P[j+1..m-1] is a suffix of P[0..k] and P[j] != P[k-m+j+1]

or

P[0..k] is a suffix of P[j+1..m-1]

COMP526 Unit 4-4 2020-03-03 String Matching: Boyer-Moore

Knuth–Morris–Pratt Algorithm

On the way of the KMP algorithm, T and P are matched each character sequentially from left to right at the beginning, which is similar to the Brute Force algorithm. Not only that, but the KMP algorithm also uses the information from the pattern itself to avoid re-examine the characters that are anyway matched when a mismatch occurs.

Partial Match table (also known as “failure function”) can help determine the shift rules of P through pre-processing the pattern itself and compile a list of all possible fallback positions that bypass a maximum of hopeless characters while not sacrificing any potential matches in doing so. Here, array C[] is applied to store the same information is shown below. ‘Position’ indicates the position of the mismatched character in P, let’s say j, hence j‘s range is from 0 to m-1. ‘Prefix’ refers to the sub-pattern starting at P[0] and ending at P[j]. For each sub-pattern P[0..j], C[j] stores length of the maximum matching proper prefix which is also a suffix of the sub-pattern P[0..j].

       C[j] = the longest proper prefix of P[0..j] 
              which is also a suffix of P[0..j].

When a mismatch occurs,

  • It’s known that P[0..j-1] match with T[i-j…i-1] (Note that j starts with 0 and increment it only when there is a match). 
  • From the above definition, it’s also known that C[j-1] is the count of characters of P[0…j-1] that are both proper prefix and suffix. 
  • According to the above two points, it’s not necessary to match the characters of P[0…j-1] with T[i-j…i-1] again because these characters will anyway match.
  • Therefore, just shift P by j - C[j-1], and start matching.

Efficiency

AlgorithmsProcessing TimeMatching TimeSpace
Brute ForceΘ(mn)
Rabin-KarpΘ(m)average Θ(n + m),
worst Θ((n−m)m)
O(1)
Boyer-MooreΘ(m + k)best Ω(n/m),
worst O(mn)
Θ(k)
Knuth–Morris–PrattΘ(m)Θ(n)Θ(m)
String-searching algorithm