String Matching with Finite Automata and Knuth Morris Pratt Algorithm

Algorithm to search for a given pattern in a text using Finite Automata and Knuth-Morris-Pratt's Technique.

1. String Matching with Finite Automata
Dr.Kiran K
Assistant Professor
Department of CSE
UVCE
Bengaluru, India.

2. Finite Automata
AFiniteAutomataisa5-tuple(Q,q
0,A,∑,δ),where
•Q : FinitesetofStates
•q
0єQ : StartState
•ACQ : DistinguishedsetofAcceptingStates
•∑ : FiniteInputAlphabet
•δ : TransitionFunction.AfunctionfromQx∑intoQ,
•Φ : Final-StateFunctionfrom∑*toQsuchthatΦ(w)isthe
stateMendsupinafterscanningthestringw.
MacceptsastringwiffΦ(w)єA.
Φ(ε)=q
0
Φ(ε)=δ(Φ(w),a)forwє∑*,aє∑

3. Finite Automata…
•Thefiniteautomatonbeginsinstateq
0andreadsthecharactersofitsinputstring
oneatatime.
•Iftheautomatonisinstateqandreadsinputcharactera,itmoves(“makesa
transition”)fromstateqtostateδ(q,a).
•WheneverthecurrentstateqisamemberofA,themachineMhasacceptedthe
stringreadsofar.
•Aninputthatisnotacceptedisrejected.

4. Finite Automata…
Q={0,1}
q
0=0
∑={a,b}
State Transition Diagram
State 1: Accepting State
Directed Edges: Transitions
abaaa: Enters states <0, 1, 0, 1, 0, 1>; Accepts.
abbaa: Enters states <0, 1, 0, 0, 1, 0>; Rejects.
Eg.: Finite Automata that accepts strings ending with odd number of a’s
Transition Function,δ
Input
State a b
0 1 0
1 0 0

5. String Matching Automata
•AStringMatchingAutomatonisconstructedforagivenpatternPinthe
Preprocessingstep.
•SuffixFunction(σ):
Anauxiliaryfunctionthatspecifiesthestring-matchingautomaton
correspondingtoagivenpatternP[1..m].
Itmaps∑*to{0,1,...,m}suchthatσ(x)isthelengthofthelongestprefix
ofPthatisalsoasuffixofx:σ(x)=max{k:P
kx}.
P
0=εisasuffixofeverystring.
ForapatternPoflengthm,σ(x)=miffPx
xy→σ(x)≤σ(y)
Eg.:P=ab
σ(ε)=0
σ(ccaca)=1
σ(ccab)=2

6. String Matching Automata…
TheString-MatchingAutomatonthatcorrespondstoagivenpatternP[1..m]is
definedasfollows:
•ThestatesetQis{0,1,...,m}.
State0-Startstate,q
0;
Statem-Acceptingstate.
•Thetransitionstateforanystateqandcharacterxisdefinedas:
δ(q,x)=σ(P
qx)
Note:ThetransitionfunctionδkeepstrackofthelongestprefixofthepatternP
thathasmatchedthetextstringTsofar.

7. String Matching Automata…
δ(q,x)=σ(P
qx)?
•IfthesubstringendingatT[i]matchessomeprefixP
jofP,thenP
jmustbea
suffixofT
i.
•If(q=Φ(T
i),theautomatonisinstateqafterreadingT
i
•Instateq,(P
qT
i)and(q=σ(T
i))
•Thus,δisdefinedtogivethelengthofthelongestprefixofPthatmatchesa
suffixofT
i
Note:Φ(T
i)andσ(T
i)bothequalq,thustheautomatonmaintainstheinvariant:
Φ(T
i)=σ(T
i)

8. String Matching Automata…
•IftheautomatonisinstateqandreadsthenextcharacterT[i+1]=x,itenters
thestateσ(T
ix)ifthelongestprefixofPisasuffixofT
ix.
•P
qisthelongestprefixofPthatisasuffixofT
i→σ(P
qx)isthelongestprefix
ofPthatisasuffixofT
ix.
•Therearetwocases:
Case1:x=P[q+1]
Characterxcontinuestomatchthepattern.
δ(q,a)=q+1.
Case2:x≠P[q+1]
Characterxdoesnotcontinuetomatchthepattern.
FindasmallerprefixofPthatisalsoasuffixofT
i.

9. Example
P=ababaca
δ(q,x)=σ(P
qx)
q=0
P
0=ε; x={a,b,c}
δ(0,a)=σ(a)=1(aisthelongestprefixofthepatternababaca)
δ(0,b)=σ(b)=0(bisthenotaprefixofthepatternababaca)
δ(0,c)=σ(c)=0(cisthenotaprefixofthepatternababaca)
0
0 1
a

10. Example…
P=ababaca
δ(q,x)=σ(P
qx)
q=1
P
1=a; x={a,b,c}
δ(1,a)=σ(aa)=1(aisthelongestprefixofthepatternababaca)
δ(1,b)=σ(ab)=2(abisthelongestprefixofthepatternababaca)
δ(1,c)=σ(ac)=0(Nosuffixofacisaprefixofthepatternababaca)
20 1
a b
a

11. Example…
P=ababaca
δ(q,x)=σ(P
qx)
q=2
P
2=ab; x={a,b,c}
δ(2,a)=σ(aba)=3(abaisthelongestprefixofthepatternababaca)
δ(2,b)=σ(abb)=0(Nosuffixofabbisaprefixofthepatternababaca)
δ(2,c)=σ(abc)=0(Nosuffixofabcisaprefixofthepatternababaca)
3
a
20 1
a b
a

12. Example…
P=ababaca
δ(q,x)=σ(P
qx)
q=3
P
3=aba;x={a,b,c}
δ(3,a)=σ(abaa)=1(aisthelongestprefixofthepatternababaca)
δ(3,b)=σ(abab)=4(ababisthelongestprefixofthepatternababaca)
δ(3,c)=σ(abac)=0(Nosuffixofabacisaprefixofthepatternababaca)
3
a
20 1
a b
a
4
b
a

13. Example…
P=ababaca
δ(q,x)=σ(P
qx)
q=4
P
4=abab;x={a,b,c}
δ(4,a)=σ(ababa)=5(ababaisthelongestprefixofthepatternababaca)
δ(4,b)=σ(ababb)=0(Nosuffixofababbisaprefixofthepatternababaca)
δ(4,c)=σ(ababc)=0(Nosuffixofababcisaprefixofthepatternababaca)
3
a
20 1
a b
a
4
b
a
5
a

14. Example…
P=ababaca
δ(q,x)=σ(P
qx)
q=5
P
5=ababa;x={a,b,c}
δ(5,a)=σ(ababaa)=1(aisthelongestprefixofthepatternababaca)
δ(5,b)=σ(ababab)=4(ababisthelongestprefixofthepatternababaca)
δ(5,c)=σ(ababac)=6(ababacisthelongestprefixofthepatternababaca)
a
3
a
20 1
a b
a
4
b
a
5 6
a
b
c

15. Example…
P=ababaca
δ(q,x)=σ(P
qx)
q=6
P
6=ababac;x={a,b,c}
δ(6,a)=σ(ababaca)=7(ababacaisthelongestprefixofthepatternababaca)
δ(6,b)=σ(ababacb)=0(Nosuffixofababacbisaprefixofthepatternababaca)
δ(6,c)=σ(ababacc)=0(Nosuffixofababaccisaprefixofthepatternababaca)
a
73
a
20 1
a b
a
4
b
a
5 6
a
b
c a

16. Example…
P=ababaca
δ(q,x)=σ(P
qx)
q=7
P
7=ababaca; x={a,b,c}
δ(7,a)=σ(ababacaa)=1(aisthelongestprefixofthepatternababaca)
δ(7,b)=σ(ababacab)=2(abisthelongestprefixofthepatternababaca)
δ(7,c)=σ(ababacac)=0(Nosuffixofababacacisaprefixofthepatternababaca)
b
a
73
a
20 1
a b
a
4
b
a
5 6
a
b
c a
a

17. Example…
Transition Function,δ
Input
Statea b c
0 1 0 0
1 1 2 0
2 3 0 0
3 1 4 0
4 5 0 0
5 1 4 6
6 7 0 0
7 1 2 0
b
a
73
a
20 1
a b
a
4
b
a
5 6
a
b
c a
a
State-Transition Diagram for the String-Matching Automaton
that Accepts all Strings ending in the String ababaca.

18. COMPUTE-TRANSITION-FUNCTION(P,∑)
m=P.length
For(q=0tom)
For(Eachcharacterxϵ∑)
k=min(m+1,q+2)
Repeat
k=k–1
Until(P
kP
qx)
δ(q,x)=k
Returnδ
Transition Function Algorithm
Running Time: O (m
3
| ∑ |)
Outer For Loop: mtimes.
Inner For Loop: m x | ∑ | times
∑times for each value of m.
Repeat Loop: (m x | ∑ |) x m
2
times
Repeatloopmaximumm+1times,
withthetestP
k P
qxrequiring
uptomcharactercomparisons.

19. Example
P=ababaca;m=7;k=min(m+1,q+2)P
kP
qx δ(q,x)=k
q= 0; k= min (7+ 1, 0+ 2) = min (8, 2) = 2
x= a
p
0 a = a
k = 1; p
1 = a; aa
δ(0, a) = 1
x= b
p
0 b = b
k = 1; p
1 = a; ab
k = 0; p
0 = ε;εb
δ(0, b) = 0
x= c
p
0 c= c
k = 1; p
1= a; ac
k = 0; p
0= ε;εb
δ(0, c) = 0
q= 1; k= min (7+ 1, 1+ 2) = min (8, 3) = 3
x= a
p
1 a= aa
k = 2; p
2 = ab; abaa
k = 1; p1= a; aaa
δ(1, a) = 1
x= b
p
1 b= ab
k = 2; p
2 = ab; abab
δ(1, b) = 2
x= c
p
1 c= ac
k = 2; p
2 = ab; abac
k = 1; p
1 = a; aac
k = 0; p
0 = ε;εac
δ(1, c) = 0

20. Example…
P=ababaca;m=7;k=min(m+1,q+2)P
kP
qx δ(q,x)=k
q= 2; k= min (7+ 1, 2 + 2) = min (8, 2) = 4
x= a
p
2a = aba
k = 3; p
3 = aba; abaaba
δ(2, a) = 3
x= b
p
2 b = abb
k = 3; p
3 = aba; abaabb
k = 2; p
2 = ab; ababb
k = 1; p
1= a; aabb
k = 0; p
0 = ε;εabb
δ(2, b) = 0
x= c
p
2 c = abc
k = 3; p
3 = aba; abaabc
k = 2; p
2 = ab; ababc
k = 1; p
1= a; aabc
k = 0; p
0 = ε;εabc
δ(2, c) = 0

21. Example…
P=ababaca; m=7; k=min(m+1,q+2) P
kP
qx δ(q,x)=k
q= 3; k= min (7+ 1, 3+ 2) = min (8, 5) = 5
x= a
p
3 a = abaa
k = 4; p
4 = abab; abababaa
k = 3; p
3 = aba; abaabaa
k = 2; p
2 = ab; ababaa
k = 1; p1= a; aabaa
δ(3, a) = 1
x= b
p
3b =abab
k = 4; p
4 = abab; abababab
δ(3, b) = 4
x= c
p
3c =abac
k = 4; p
4 = abab; abababac
k = 3; p
3 = aba; abaabac
k = 2; p
2 = ab; ababac
k = 1; p1= a; aabac
k = 0; p
0 = ε;εabac
δ(3, c) = 0

22. Example…
P=ababaca; m=7; k=min(m+1,q+2) P
kP
qx δ(q,x)=k
q= 4; k= min (7+ 1, 4+ 2) = min (8, 6) = 6
x= a
p
4 a = ababa
k=5;p
5=ababa;ababaababa
δ(4, a) = 5
x= b
p
4b =ababb
k=5;p
5=ababa;ababaababb
k=4;p
4=abab;ababababb
k=3;p
3=aba;abaababb
k=2;p
2=ab;abababb
k=1;p
1=a;aababb
k=0;p
0=ε;εababb
δ(4, b) = 0
x= c
p
4 c = ababc
k=5;p
5=ababa;ababaababc
k=4;p
4=abab;ababababc
k=3;p
3=aba;abaababc
k=2;p
2=ab;abababc
k=1;p
1=a;aababc
k=0;p
0=ε;εababc
δ(4, c) = 0

23. Example…
P=ababaca; m=7; k=min(m+1,q+2) P
kP
qx δ(q,x)=k
q= 5; k= min (7+ 1, 5+ 2) = min (8, 7) = 7
x= a
p
5a =ababaa
k = 6; p
6 = ababac; ababacababaa
k = 5; p
5 = ababa; ababaababaa
k = 4; p
4 = abab; ababababaa
k = 3; p
3 = aba; abaababaa
k = 2; p
2 = ab; abababaa
k = 1; p
1 = a; aababaa
δ(5, a) = 1
x= b
p
5b =ababab
k = 6; p
6 = ababac; ababacababab
k = 5; p
5 = ababa; ababaababab
k = 4; p
4 = abab; ababababab
δ(5, b) = 4
x= c
p
5c =ababac
k = 6; p
6 = ababac; ababacababac
δ(5, c) = 6

24. Example…
P=ababaca; m=7; k=min(m+1,q+2) P
kP
qx δ(q,x)=k
q= 6; k= min (7+ 1, 6+ 2) = min (8, 8) = 8
x= a
p
6a =ababaca
k = 7; p
7 = ababaca; ababacaababaa
δ(6, a) = 7
x= b
p
6 b = ababacb
k = 7; p
7 = ababaca; ababacaababacb
k = 6; p
6 = ababac; ababacababacb
k = 5; p
5 = ababa; ababaababacb
k = 4; p
4 = abab; ababababacb
k = 3; p
3 = aba; abaababacb
k = 2; p
2 = ab; abababacb
k = 1; p
1 = a; aababacb
k = 0; p
0 = ε; εababacb
δ(6, b) = 0
x= c
p
6c =ababacc
k = 7; p
7=ababaca; ababacaababacc
k = 6; p
6=ababac; ababacababacc
k = 5; p
5=ababa; ababaababacc
k = 4; p
4=abab; ababababacc
k = 3; p
3=aba; abaababacc
k = 2; p
2=ab; abababacc
k = 1; p
1=a; aababacc
k = 0; p
0=ε; εababacc
δ(6, c) = 0

25. Example…
P=ababaca; m=7; k=min(m+1,q+2) P
kP
qx δ(q,x)=k
q= 7; k= min (7+ 1, 7+ 2) = min (9, 8) = 8
x= a
p
7a =ababacaa
k = 7; p
7 = ababaca; ababacaababacaa
k = 6; p
6 = ababac; ababacababacaa
k = 5; p
5 = ababa; ababaababacaa
k = 4; p
4 = abab; ababababacaa
k = 3; p
3 = aba; abaababacaa
k = 2; p
2 = ab; abababacaa
k = 1; p
1 = a; aababacaa
δ(7, a) = 1
x= b
p
7b =ababacab
k = 7; p
7 = ababaca; ababacaababacab
k = 6; p
6 = ababac; ababacababacab
k = 5; p
5 = ababa; ababaababacab
k = 4; p
4 = abab; ababababacab
k = 3; p
3 = aba; abaababacab
k = 2; p
2 = ab; abababacab
δ(7, b) = 2
x= c
p
7c =ababacac
k = 7; p
7 = ababaca; ababacaababacac
k = 6; p
6 = ababac; ababacababacac
k = 5; p
5 = ababa; ababaababacac
k = 4; p
4 = abab; ababababacac
k = 3; p
3 = aba; abaababacac
k = 2; p
2 = ab; abababacac
k = 1; p
1 = a; aababacac
k = 0; p
0 = ε; εababacac
δ(7, c) = 0

26. Example…
Transition Function,δ
Input
Statea b c
0 1 0 0
1 1 2 0
2 3 0 0
3 1 4 0
4 5 0 0
5 1 4 6
6 7 0 0
7 1 2 0

27. For any string yand character x, we have σ(yx) ≤ σ(y) + 1
With reference to the figure, Let r= σ(yx) (L1.1)
Case1:Let, r= 0 (L1.2)
(L1.1) and (L1.2) → σ(yx) = r = 0 (L1.3)
wktσ(y) ≥ 0 (σ cannot be negative) (L1.4)
(L1.3) and (L1.4)→ 0 ≤ σ(y) + 1 (L1.5)
(L1.3) and (L1.4) → σ(yx)≤ σ(y) + 1
Suffix-Function Inequality
P
r –1 x
P
r
y

28. Case2:Let, r> 0 (L1.6)
wktσ(y) = max {k: P
ky}(Suffix Definition) (L1.7)
(L1.1), (L1.6) and (L1.7) → P
ryx (L1.8)
(L1.8) → P
r –1 y (L1.9)
(L1.7) and (L1.9) → r–1 ≤ σ(y) (L1.10)
(L1.10) → r≤ σ(y) + 1 (L1.11)
(L1.1) and (L1.11) → σ(yx) ≤ σ(y) + 1
Suffix-Function Inequality…

29. For any string yand character x, if q= σ(y), then σ(yx) = σ(P
qx)
Wkt, σ(y) = max {k: P
ky}(Suffix Definition) (L2.1)
Also, P
qxyx (From the Figure) (L2.2)
Let, r= σ(yx) (L2.3)
(L2.3) →P
r yx (L2.4)
Wkt, σ(yx) ≤ σ(y) + 1 (Suffix-Function inequality Lemma)(L2.5)
Also, q= σ(y) (Given) (L2.6)
(L2.3), (L2.5) and (L2.6) → r≤ q+ 1 (L2.7)
Suffix-Function Recursion Lemma
x
P
q x
P
r
y

30. Wkt, |P
r| = r and|P
qx| = q+ 1 (L2.8)
(L2.7) and (L2.8) → |P
r| ≤ |P
qx| (L2.9)
(L2.2), (L2.4) and (L2.9) → P
r P
qx (Overlapping-Suffix Lemma) (L2.10)
Wkt, x y → σ(x) ≤ σ(y) (L2.11)
(L2.10) and (L2.11) → r≤ σ(P
qx) (L2.12)
(L2.3) and (L2.12) → σ(yx) ≤ σ(P
qx) (L2.13)
(L2.2) and (L2.11) → σ(P
qx) ≤ σ(yx) (L2.14)
(L2.13) and (L2.14) → σ(yx) = σ(P
qx)
Suffix-Function Recursion Lemma…

31. FINITE-AUTOMATON-MATCHER (T,δ, m)
n= T.length
q=0
For(i= 1 to n)
q=δ(q, T [i])
If(q== m)
Print “Pattern occurs with shift” i–m
Running Time: Ө(n)
Matching Algorithm

32. T = abababacaba; P= ababaca q= δ(q, T [i])
n= T.length= 11; m= 7
q=0
i= 1, q= δ(0, T [1]) = δ(0, a) = 1
q≠ m→ i= 2, q= δ(1, T [2]) = δ(1, b) = 2
q≠ m→ i= 3, q= δ(2, T [3]) = δ(2, a) = 3
q≠ m→ i= 4, q= δ(3, T [4]) = δ(3, b) = 4
q≠ m → i= 5, q= δ(4, T [5]) = δ(4, a) = 5
q≠ m → i= 6, q= δ(5, T [6]) = δ(5, b) = 4
q≠ m → i= 7, q= δ(4, T [7]) = δ(4, a) = 5
q≠ m → i= 8, q= δ(5, T [8]) = δ(5, c) = 6
q≠ m → i= 9, q= δ(6, T [9]) = δ(6, a) = 7
q = m → Pattern occurs with shifti–m= 9 –7 = 2
Example
Transition Function,δ
Input
Statea b c
0 1 0 0
1 1 2 0
2 3 0 0
3 1 4 0
4 5 0 0
5 1 4 6
6 7 0 0
7 1 2 0

33. Theorem
IfΦisthefinal-statefunctionofastring-matchingautomatonforagivenpatternPand
T[1..n]isaninputtextfortheautomaton,thenΦ(T
i)=σ(T
i)fori=0,...,n.
Proof:
Basis:Fori=0
T
0=ε
→Φ(T
0)=0=σ(T
0)
Assumption:Let,Φ(T
i)=σ(T
i)
Induction:
Letq=Φ(T
i)and
x=T[i+1]

34. Theorem…
Φ(T
i+1) = Φ(T
ix)
= δ(Φ(T
i),x)
= δ(q,x) (Φ(T
i)=q)
= σ(P
qx) (δ(q,x)=σ(P
qx))
= σ(T
ix) (Suffix-functionrecursionlemma)
= σ(T
i+1)
Whenthemachineentersstateqinthealgorithmbyexecutingthestatement
q=δ(q,T[i]),qisthelargestvaluesuchthatP
qT[i].
→q=miffmachinehasjustscannedanoccurrenceofthepatternP.
ThustheFINITEAUTOMATON-MATCHERoperatescorrectly

35. Knuth-Morris-Pratt Algorithm

36. Introduction
•Thisalgorithmavoidscomputingthetransitionfunctionδ.
•Itusesanauxiliaryfunctionᴨ,calledthePrefixFunction,whichisprecomputed
fromthepatternoflengthm,andstoredinanarrayᴨ[1..m].
•Foranystateq=0,1,...,mandanycharacterxє∑thevalue,ᴨ[q]contains
theinformationneededtocomputeδ(q,x)butdoesnotdependonx.
•Arrayᴨcontainsonlymentries,whereasδhasӨ(m|∑|)entries.Hence,
computingᴨsavesafactorof|∑|inthepreprocessingtimecomparedto
computingδ.
•ThealgorithmhasapreprocessingtimeofӨ(m)andamatchingtimeofӨ(n).

37. Prefix Function
Theprefixfunctionᴨforapatternencapsulatesknowledgeabouthowthepattern
matchesagainstshiftsofitself.Thisinformationhelpstoavoidtestinguseless
shiftsinthenaivepattern-matchingalgorithmandtoavoidprecomputingthefull
transitionfunctionδforastring-matchingautomaton.
Eg.:T=bacbababaabcbab P=ababaca
•ConsidertheshiftsasshowninthefigureusingaNaïvestringMatcher.
•q=5charactershavematchedsuccessfully,butthe6
th
characterfailstomatch.

38. Prefix Function…
•Theinformationthatqcharactershavematchedsuccessfullydeterminesthe
correspondingtextcharacters.
•Knowingtheseqtextcharactersallowstodetermineimmediatelythatcertain
shiftsareinvalid.Eg.:s+1isinvalidasitalignsthefirstcharacterofthepattern
‘a’withcharacter‘b’oftext.
•Theshiftsʹ=s+2alignsthefirst3charactersofthepatternwiththetextthat
match.
•sʹcanbecomputedasfollows:
IfpatterncharactersP[1..q]matchtextcharactersT[s+1..s+q],the
leastshiftsʹ>ssuchthatforsomek<q,P[1..k]=T[sʹ+1..sʹ+k]
wheresʹ+k=s+q.i.e.,

39. Prefix Function…
IfP
qT
s+qisknown,findthelongestprefixP
kofP
qthatisalsoasuffixof
T
s+q
Thenewshiftsʹisfoundbyaddingthedifference(q–k)tos
s=sʹ+(q–k)
Note:
•Ifk=0thens=sʹ+qandalltheshiftss+1,s+2,,,s+q–1areruledout
anditisthebestshift.
•Atthenewshiftsʹ,thefirstkcharactersofPneednotbecomparedwiththe
correspondingcharactersofTbecausesʹiscomputedafterensuring
P[1..k]=T[sʹ+1..sʹ+k].

40. Prefix Function…
sʹcanbecomputedasfollowsbycomparingthepatternwithitselfasfollows:
•SinceT[sʹ+1..sʹ+k]ispartoftheknownportionofthetext
itisasuffixofthestringP
q.
•Hence,P[1..k]=T[sʹ+1..sʹ+k]→Findthegreatestk<qsuchthat
P
kP
q.
FormalDefinition:
GivenapatternP[1..m],theprefixfunctionforthepatternPisthefunction
ᴨ:[1..m]→{0,1,...,m–1}suchthatᴨ[q]=max{k:k<qandP
kP
q}.
Note:
Itconvenienttostore,foreachvalueofq,thenumberkofmatchingcharactersat
thenewshiftsʹ.

41. Example
Pattern:ababaca; P
kP
q k<q
i=1; q=1; P
1=a; k<1; P
k=ε
ᴨ[1]=0 (εisthelongestprefixofa)
i=2; q=2; P
2=ab; k<2; P
k=ε
ᴨ[2]=0 (Noprefixofsize<2,(a),isasuffixofabexceptε)
i=3; q=3; P
3=aba; k<3; P
k=a
ᴨ[3]=1 (aisthelongestprefixwithsize<3,thatisasuffixofaba)
i=4; q=4; P
4=abab; k<4; P
k=ab
ᴨ[4]=2 (abisthelongestprefixwithsize<4,thatisasuffixofabab)
i=5; q=5; P
q=ababa; k<5; P
k=aba
ᴨ[5]=3 (abaisthelongestprefixwithsize<4,thatisasuffixofababa)

42. Example…
Pattern:ababaca; P
kP
q
i=6;q=6;P
q=ababac;k<6; P
k=ε
ᴨ[6]=0 (Noprefixofsize<6,(ababa,abab,aba,
ab,a),isasuffixofababacexceptε)
i=7;q=7;P
q=ababaca;k<7; P
k=a
ᴨ[7]=1 (aisthelongestprefixwithsize<7,thatis
asuffixofababaca)
i ᴨ[i]
1 0
2 0
3 1
4 2
5 3
6 0
7 1

43. Prefix Function Algorithm
COMPUTE-PREFIX-FUNCTION(P)
m=P.length
LetΠ[1..m]beanewarray
Π[1]=0
k=0
For(q=2tom)
While(k>0andP[k+1]≠P[q])
k=Π[k]
If(P[k+1]==P[q])
k=k+1
Π[q]=k
returnΠ
RunningTime:Θ(m)
1.Forloopincreasesthevalueofkonce
foreachiterationandhencethetotal
increaseinkisatmostm–1.
2.k<qensuringthatΠ[q]<qwhich
meansthateachiterationofthewhile
loopdecrementsk.
3.kneverbecomesnegative.
Thesefactsputtogether,itisobserved
thattotaldecreaseinkfromthewhile
loopisboundedfromabovebythetotal
increaseinkoveralliterationsofthefor
loop,whichism–1.

44. Example
For(q=2tom)
While(k>0andP[k+1]≠P[q])
k=Π[k]
If(P[k+1]==P[q])
k=k+1
Π[q]=k
P = ababaca
Π[1] = 0; k= 0;
q= 2; k= 0;
While loop: not executed (k= 0);
If condition: Fails (a≠ b;P [1] ≠ P[2]));
Π[2] = 0;
q= 3; k= 0;
While loop: not executed (k= 0)
If condition: (a== a; (P [1] == P[3])); → k= 0 + 1 = 1;
Π[3] = 1;
q= 4; k= 1;
While loop: not executed (b= b;(P [2] == P[4]))
If condition: (b == b; (P[2] == P[4])); →k= 1 + 1 = 2;
Π[4] = 2

45. Example…
q= 5; k= 2;
While loop: not executed (a= a; (P[3] == P[5]))
If condition: (a== a;(P [3] == P[5])); →k= 2 + 1 = 3;
Π[5] = 3
q= 6; k= 3;
While loop: b≠ c; (P [4] ≠ P [6]); → k= Π[3] = 1
b≠ c;(P [2] ≠ P [6]); → k= Π[1] = 0
If condition: Fails (a≠ c; (P [1] ≠ P [6]))
Π[6] = 0
q= 7; k= 0;
While loop: not executed (k= 0)
If condition: (a== a; (P [1]= = P [7]));k= 0 + 1 = 1;
Π[7] = 1
i ᴨ[i]
1 0
2 0
3 1
4 2
5 3
6 0
7 1
For(q=2tom)
While(k>0andP[k+1]≠P[q])
k=Π[k]
If(P[k+1]==P[q])
k=k+1
Π[q]=k

46. Matching Algorithm
KMP-MATCHER (T, P)
n= T.length
m= P.length
Π= COMPUTE-PREFIX-FUNCTION (P)
q= 0
For (i= 1 to n)
While (q> 0 and P[q+ 1] ≠ T[i])
q= Π[q]
If (P[q+ 1] == T[i])
q= q+ 1
If (q== m)
Print “Pattern occurs with shift” i–m + 1
q= Π[q]
RunningTime:Θ(n)
1.Forloopincreasesthevalueofqonce
foreachiterationandhencethetotal
increaseinqisatmostn.
2.Π[q]<qwhichmeansthateachiteration
ofthewhileloopdecrementsq.
3.qneverbecomesnegative.
Thesefactsputtogether,itisobservedthat
totaldecreaseinqfromthewhileloopis
boundedfromabovebythetotalincreaseinq
overalliterationsoftheforloop,whichisn.

47. Example
For (i= 1 to n)
While (q> 0and P[q+ 1] ≠ T[i])
q= Π[q]
If (P[q+ 1] == T[i])
q= q+ 1
If (q== m)
Print “Pattern occurs with shift” i–m +1
q= Π[q]
T: bacbababaababacababa;n= 20
P: ababaca; m= 7
i= 1; q= 0
While loop: not executed (q= 0)
If condition: fails (a≠ b; (P [1] ≠ T [1]))
q≠ m
i= 2; q= 0
While loop: not executed (q= 0)
If condition: (a== a; (P [1] == T [2])); q = 0 + 1 = 1
q≠ m
i= 3; q= 1
While loop: (b≠c; (P [2] ≠ T [3])); q= Π[1] = 0
If condition: Fails (b≠c; (P [2] ≠ T [3]));
q≠ m
i= 4; q= 0
While loop: not executed (q= 0)
If condition: Fails (a≠b; (P [1] ≠ T [4]));
i ᴨ[i]
1 0
2 0
3 1
4 2
5 3
6 0
7 1

48. Example…
T: bacbababaababacababa; n= 20
P: ababaca; m= 7
q≠ m
i= 5; q= 0
While loop: not executed (q= 0)
If condition: (a== a; (P [1] == T [5])); q = 0 + 1 = 1
q≠ m
i= 6; q= 1
While loop: not executed (b== b; (P[2] == T[6]))
If condition: (b== b; (P [2] == T [6])); q = 1 + 1 = 2
q≠ m
i= 7; q= 2
While loop: not executed (a== a; (P[3] == T[7]))
If condition: (a== a; (P [3] == T [7])); q = 2 + 1 = 3
i ᴨ[i]
1 0
2 0
3 1
4 2
5 3
6 0
7 1
For (i= 1 to n)
While (q> 0and P[q+ 1] ≠ T[i])
q= Π[q]
If (P[q+ 1] == T[i])
q= q+ 1
If (q== m)
Print “Pattern occurs with shift” i–m +1
q= Π[q]

49. Example…
T: bacbababaababacababa; n= 20
P: ababaca; m= 7
q≠ m
i= 8; q= 3
While loop: not executed (b== b; (P[4] == T[8]))
If condition: (b== b; (P [4] == T [8])); q = 3 + 1 = 4
q≠ m
i= 9; q= 4
While loop: not executed (a== a; (P[5] == T[9]))
If condition: (a== a; (P [5] == T [9])); q = 4 + 1 = 5
q≠ m
i= 10; q= 5
While loop: (c≠a; (P[6] ≠T[10])); q= Π[5] = 3
(b≠ a; (P[4] ≠ T[10])); q= Π[3] = 1
(b≠ a; (P[2] ≠ T[10])); q= Π[1] = 0
If condition:(a== a;(P [1] == T [10]));q = 0 + 1 = 1
i ᴨ[i]
1 0
2 0
3 1
4 2
5 3
6 0
7 1
For (i= 1 to n)
While (q> 0and P[q+ 1] ≠ T[i])
q= Π[q]
If (P[q+ 1] == T[i])
q= q+ 1
If (q== m)
Print “Pattern occurs with shift” i –m +1
q= Π[q]

50. Example…
T: bacbababaababacababa; n= 20
P: ababaca; m= 7
q≠ m
i= 11; q= 1
While loop: not executed (b== b; (P[2] == T[11]));
If condition:(b== b;(P [2] == T [11]));q = 1 + 1 = 2
q≠ m
i= 12; q= 2
While loop:notexecuted (a== a; (P[3] == T[12]));
If condition:(a== a;(P [3] == T [12]));q = 2 + 1 = 3
q≠ m
i= 13; q= 3
While loop:notexecuted (b== b; (P[4] == T[13]));
If condition:(b== b;(P [4] == T [13]));q = 3 + 1 = 4
i ᴨ[i]
1 0
2 0
3 1
4 2
5 3
6 0
7 1
For (i= 1 to n)
While (q> 0and P[q+ 1] ≠ T[i])
q= Π[q]
If (P[q+ 1] == T[i])
q= q+ 1
If (q== m)
Print “Pattern occurs with shift” i –m +1
q= Π[q]

51. Example…
T: bacbababaababacababa; n= 20
P: ababaca; m= 7
q≠ m
i= 14; q= 4
While loop:notexecuted (a== a; (P[5] == T[14]));
If condition:(a== a;(P [5] == T [14]));q = 4 + 1 = 5
q≠ m
i= 15; q= 5
While loop:notexecuted (c== c; (P[6] == T[15]));
If condition:(c== c;(P [6] == T [15]));q = 5 + 1 = 6
q≠ m
i= 16; q= 6
While loop:notexecuted (a== a; (P[7] == T[16]));
If condition:(a== a;(P [7] == T [16]));q = 6 + 1 = 7
q== m
Pattern occurs with shift i–m+ 1 = 16 –7 + 1 = 10
i ᴨ[i]
1 0
2 0
3 1
4 2
5 3
6 0
7 1
For (i= 1 to n)
While (q> 0and P[q+ 1] ≠ T[i])
q= Π[q]
If (P[q+ 1] == T[i])
q= q+ 1
If (q== m)
Print “Pattern occurs with shift” i–m +1
q= Π[q]
RunningTime:Θ(m)

52. Prefix-Function Iteration Lemma
LetPbeapatternoflengthmwithprefixfunctionΠ.Thenforq=1,2,...,m,wehave
Π*[q]={k:k<qandP
kP
q}
Proof:
Step1:ProveΠ*[q]{k:k<qandP
kP
q}≡iЄΠ*[q]→P
iP
q–ByInduction
iЄΠ*[q] (Given) (L1.1)
(L1.1)→i=Π
(u)
[q]forsomeu>0 (L1.2)
Basis:u=1 (L1.3)
(L1.2)and(L1.3)→i=Π[q] (L1.4)
wkt,i<q (L1.5)
ᴨ[q]=max{k:k<qandP
kP
q} (L1.6)
(L1.4)(L1.5)and(L1.6)→P
Π[q]P
q (L1.7)
Induction:(L1.4)and(L1.5)→Π[i]<i (L1.8)
(L1.6)and(L1.8)→P
Π[i]P
i (L1.9)
wkt,<andaretransitive (L1.10)
(L1.8),(L1.9)and(L1.10)→P
Π[i]P
iforalli (L1.11)
(L1.7)and(L1.11)→Π*[q]{k:k<qandP
kP
q}(L1.12)

53. Prefix-Function Iteration Lemma…
Step2:Prove{k:k<qandP
kP
q}Π*[q]–ByContradiction
Assume{k:k<qandP
kP
q}–Π*[q]isnonempty (L1.13)
Letjbethelargestintegerinthesetin(L1.13) (L1.14)
(L1.6)→Π[q]isthelargestvaluein{k:k<qandP
kP
q} (L1.15)
wkt,Π[q]ЄΠ*[q] (DefinitionofΠ*[q]) (L1.16)
(L1.14)and(L1.15)→j<Π[q] (L1.17)
(L1.13)→jЄΠ[q] (L1.18)
From(L1.13)and(L1.17),LetjʹdenotethesmallestintegerinΠ*[q]>j(L1.19)
(L1.6)and(L1.14)→P
jP
q (L1.20)
(L1.15)and(L1.19)→P
jʹP
q (L1.21)
(L1.19),(L1.20)and(L1.21)→P
jP
jʹ (L1.22)
(L1.20),(L1.21)and(L1.22)→jisthelargestvalue<jʹ (L1.23)
(L1.23)→Π[jʹ]=j (L1.24)
(L1.1),(L1.2)and(L1.24)→jЄΠ*[q] (L1.25)
(L1.25)contradictstheassumption (L1.26)
(L1.26)→{k:k<qandP
kP
q}Π*[q] (L1.27)
(L1.12)and(L1.27)→Π*[q]={k:k<qandP
kP
q}

54. Lemma
LetPbeapatternoflengthmandΠbetheprefixfunctionforP.Forq=1,2,...,m,if
Π[q]>0thenΠ[q]–1ЄΠ*[q–1]
Proof:
Letr=Π[q]>0,sothatr<qandP
rP
q (L2.1)
(L2.1)→r–1<q–1andP
r–1P
q–1 (L2.2)
(L2.2)→r–1ЄΠ*[q–1](PrefixFunctionIterationLemma)(L2.3)
(L2.1)and(L2.3)→Π[q]–1ЄΠ*[q–1]

55. Corollary
LetPbeapatternoflengthmandletΠbetheprefixfunctionforP.Forq=2,3,...,m,
0 ifE
q–1=Ø
1+max{kЄE
q–1}ifE
q–1≠Ø
Proof:
E
q–1=Ø (C1.1)
(C1.1)→thereisnokЄE
q–1(includingk=0)forwhichP
k
canbeextendedtoP
k+1andgetapropersuffixofP
q (C1.2)
(C1.2)→Π[q]=0 (C1.3)
E
q–1≠Ø (C1.4)
(C1.4)→thereexistskЄE
q–1suchthatforeachk,
k+1<qandP
k+1P
q (C1.5)
ᴨ[q]=max{k:k<qandP
kP
q} (C1.6)
(C1.5)and(C1.6)→ᴨ[q]≥1+max{kЄE
q–1} (C1.7)
(C1.7)→Π[q]>0 (C1.8)
Letr=Π[q]–1 (C1.9)
Π[q] =

56. Corollary…
(C1.9)→r+1=Π[q] (C1.10)
(C1.6)and(C1.10)→P
r+1P
q (C1.11)
(C1.8)and(C1.10)→r+1>0 (C1.12)
(C1.11)and(C1.12)→P[r+1]=P[q] (C1.13)
wkt,ifΠ[q]>0thenΠ[q]–1ЄΠ*[q–1] (Lemma) (C1.14)
(C1.8),(C1.9)and(C1.14)→rЄΠ*[q–1] (C1.15)
(C1.15)→rЄE
q–1 (C1.16)
(C1.16)→r≤max{kЄE
q–1} (C1.17)
Adding1onbothsidesof(C1.17),weget,r+1≤1+max{kЄE
q–1}(C1.18)
(C1.10)and(C1.18)→Π[q]≤1+max{kЄE
q–1} (C1.19)
(C1.7)and(C1.19)→Π[q]=1+max{kЄE
q–1} (C1.20)
0 ifE
q–1=Ø
1+max{kЄE
q–1}ifE
q–1≠Ø
(C1.3) and (C1.20) → Π[q] =

57. Correctness of Compute Prefix Function
COMPUTE-PREFIX-FUNCTION(P)
m=P.length
LetΠ[1..m]beanewarray
Π[1]=0
k=0
For(q=2tom)
While(k>0andP[k+1]≠P[q])
k=Π[k]
If(P[k+1]==P[q])
k=k+1
Π[q]=k
returnΠ
1.k=Π[q–1]atthestartofeachiterationoftheFor
loop.
•Π[1]=0andk=0whentheloopisfirstentered.
•InsuccessiveiterationsΠ[q]=k.
2.Thewhileloopandtheifconditionadjustksothat
itbecomesthecorrectvalueofΠ[q].
3.WhileloopsearchesthroughallvalueskЄΠ*[q–1]
untilitfindsavalueofkforwhichP[k+1]=P[q]
•kisthelargestvalueinthesetE
q–1.
•→Π[q]=k+1. (Corollary)
4.IftheWhileloopcannotfindakЄΠ*[q–1]such
thatP[k+1]=P[q],thenk=0.
5.IfP[1]=P[q]thenbothkandΠ[q]hastobeset
to1,otherwiseonlyΠ[q]hastobesetto0.Thisis
setcorrectlybytheifstatement.
6.ThusthefunctioncomputesΠcorrectly.

58. Similarity between Prefix function and Transition Function
1.Uponreadingacharacterx=T[i]inastateq,itmovestoanewstateδ(q,x).
StringMatchingAutomaton:
•If(x=P[q+1]),xcontinuestomatchthepatternandδ(q,x)=q+1.
•If(x≠P[q+1]),xdoesnotcontinuetomatchthepatternand0≤δ(q,x)≤q.
KMPMatcher:
•If(x=P[q+1]),xcontinuestomatchthepatternanditreachesstateq+1
withoutreferringtoΠ.
oSince(T[i]=P[q+1])),thewhileloopfailsbuttheifconditionistrueand
thusitincrementsqtoq+1.
•If(x≠P[q+1]),xdoesnotcontinuetomatchthepatternandthenewstateis
eitherqortotheleftofqalongthespineoftheautomaton.
oThewhileloopiteratesthroughthestatesinΠ*[q],stoppingeitherwhenit
arrivesinastate,sayjʹ,suchthatxmatchesP[qʹ+1])orqʹhasgoneallthe
waydownto0.
oIf(x=P[qʹ+1])thenthenewstateissettoqʹ+1whichisequaltoδ(q,x).

59. Similarity between Prefix function and Transition Function…
Example: Pattern ababaca
State q= 5
1.NextCharacter–c
•Whileloop:c=c;Fails;
•Ifcondition:c=c;true;qmovestostate6=δ(5,c).
2.NextCharacter–b
•While loop: (1) c≠ b→ q = Π(5) = 3;
(2) b=b; Fails;
•If condition: b= b; true; qmoves to state 4 = δ(5, b).
3.NextCharacter–a
•While loop: (1) c≠ a→ q = Π(5) = 3 (1
st
State in Π(5));
(2) b≠a→ q = Π(3) = 1 (2
nd
State in Π(5));
(3) b≠a→ q= Π(1) = 0(3
rd
State in Π(5));
•If condition: a= a; true; qmoves to state 1 = δ(5, a).
Transition
Function,δ
ᴨ
[i]
Input
qabc
0100
11200
23000
31401
45002
51463
67000
71201

60. Correctness of KMP-Matcher
KMP-MATCHER (T, P)
n= T.length
m= P.length
Π= COMPUTE-PREFIX-FUNCTION (P)
q= 0
For (i= 1 to n)
While (q> 0 and P[q+ 1] ≠ T[i])
q= Π[q]
If (P[q+ 1] == T[i])
q= q+ 1
If (q== m)
Print “Pattern occurs with shift” i–m
q= Π[q]
I:Showthatq=σ(T
i)withregardtotheforloopof
KMP-MatcherbyInduction:
Basis:
Initially,boththeproceduressetqto0whichisσ(T
0).
Assumption:
qʹ=σ(T
i–1),whereqʹisthestateatthestartofthefor
loop.
Induction:
WhenthecharacterT
iisconsidered,thelongestprefix
ofPthatisasuffixofT
iis:
•P
qʹ+1 (IfP[qʹ+1]=T[i])
•SomeprefixofP
qʹ
FINITE-AUTOMATON-MATCHER (T,δ, m)
n= T.length
q= 0
For(i= 1 to n)
q=δ(q, T [i])
If(q== m)
Print “Pattern occurs with shift” i–m

61. Correctness of KMP-Matcher…
KMP-MATCHER (T, P)
n= T.length
m= P.length
Π= COMPUTE-PREFIX-FUNCTION (P)
q= 0
For (i= 1 to n)
While (q> 0 and P[q+ 1] ≠ T[i])
q= Π[q]
If (P[q+ 1] == T[i])
q= q+ 1
If (q== m)
Print “Pattern occurs with shift” i–m+1
q= Π[q]
Thereare3cases:
Case1:σ(T
i)=0
•P
0=εistheonlyprefixofPthatisasuffixofT
i.
•ThewhileloopiteratesthroughthevaluesinΠ*[qʹ].
•AlthoughP
q T
iforeveryqЄΠ*[qʹ],theloop
neverfindsaqsuchthatP[qʹ+1]=T[i].
•Theloopterminateswhenqreaches0.
•TheifconditionfailssinceP[qʹ+1]≠T[i].
•Hence,q=0=σ(T
i).
Case2:σ(T
i)=qʹ+1
•P[qʹ+1]=T[i].
•Whileloopfails.
•Ifconditionistrue,andhenceqgetsincrementedto
qʹ+1=σ(T
i).
FINITE-AUTOMATON-MATCHER (T,δ, m)
n= T.length
q= 0
For(i= 1 to n)
q=δ(q, T [i])
If(q== m)
Print “Pattern occurs with shift” i–m

62. Correctness of KMP-Matcher…
KMP-MATCHER (T, P)
n= T.length
m= P.length
Π= COMPUTE-PREFIX-FUNCTION (P)
q= 0
For (i= 1 to n)
While (q> 0 and P[q+ 1] ≠ T[i])
q= Π[q]
If (P[q+ 1] == T[i])
q= q+ 1
If (q== m)
Print “Pattern occurs with shift” i–m+1
q= Π[q]
Case3:0<σ(T
i)≤qʹ (3.1)
•Thewhileloopiteratesatleastonce,checkingin
decreasingordereachvalueqЄΠ*[qʹ]untilitstops
atsomeq<qʹ.
•→P
qisthelongestprefixofP
qʹforwhich
P[qʹ+1]=T[i].
•Whenthewhileloopterminatesq+1=σ(P
qʹT[i]).
(Transitionofstateqtothenextstatewhichistothe
leftofqalongthespine). (3.2)
•(3.1)→qʹ=σ(T
i–1) (3.3)
•(3.3)→σ(T
i–1T[i])=σ(P
qʹT[i]) (3.4)
•(3.2)and(3.3)→q+1=σ(T
i–1T[i])
=σ(T
i) (3.5)
•(3.5)→q=σ(T[i])–1whenwhileloopterminates.
•Theifconditionincrementsqsotatq+1=σ(T
i).
FINITE-AUTOMATON-MATCHER (T,δ, m)
n= T.length
q= 0
For(i= 1 to n)
q=δ(q, T [i])
If(q== m)
Print “Pattern occurs with shift” i–m

63. Correctness of KMP-Matcher…
KMP-MATCHER (T, P)
n= T.length
m= P.length
Π= COMPUTE-PREFIX-FUNCTION (P)
q= 0
For (i= 1 to n)
While (q> 0 and P[q+ 1] ≠ T[i])
q= Π[q]
If (P[q+ 1] == T[i])
q= q+ 1
If (q== m)
Print “Pattern occurs with shift” i–m+1
q= Π[q]
qisassignedtoΠ[q]afteranoccurrenceofthepattern
isfoundotherwisethesearchwillproceedbymatching
P[m+1].
II.Showthatσ(T
i)=Φ(T
i)
Basis:
Fori=0,T
0=ε
→Φ(T
0)=0=σ(T
0)
Assumption:
Let,Φ(T
i)=σ(T
i)
Induction:
Letq=Φ(T
i)and
x=T[i+1]
FINITE-AUTOMATON-MATCHER (T,δ, m)
n= T.length
q= 0
For(i= 1 to n)
q=δ(q, T [i])
If(q== m)
Print “Pattern occurs with shift” i–m

64. Theorem…
Φ(T
i+1) = Φ(T
ix)
= δ(Φ(T
i),x)
= δ(q,x) (Φ(T
i)=q)
= σ(P
qx) (δ(q,x)=σ(P
qx))
= σ(T
ix) (Suffix-functionrecursionlemma)
= σ(T
i+1)
WhenthemachineentersstateqitisthelargestvaluesuchthatP
qT[i].
→q=miffmachinehasjustscannedanoccurrenceofthepatternP.
ThustheKMP-MATCHERoperatescorrectly

65. Appendix
ε : EmptyString
Ø : EmptyLanguage
∑ : FiniteInputAlphabet
∑*: languageofallstringsover∑
Eg.:If∑={0,1},then∑*={ε,0,1,00,01,10,11,000,...}istheset
ofallbinarystrings.
Overlapping-SuffixLemma:
Supposethatx,y,andzarestringssuchthatxzandyz.
If|x|≤|y|,thenxy.If|x|≥|y|,thenyx.If|x|=|y|,thenx=y.

66. Appendix…
Π*[q]:
Π*[q]={Π[q],Π
(2)
[q],Π
(3)
[q],...,Π
(t)
[q]},whereΠ
(i)
[q]isdefinedintermsof
functionaliteration,sothatΠ
(0)
[q]=qandΠ
(i)
[q]=Π[Π
(i–1)
[q]]fori≥1,andwhere
thesequenceinΠ*[q]stopsuponreachingΠ
(t)
[q]=0.
E
q–1:
Forq=2,3,...,m,definethesubsetE
q–1Π*[q–1]by
E
q–1={kЄΠ*[q–1]:P[k+1]=P[q]}
={k:k<q–1andP
kP
q–1andP[k+1]=P[q]}(PrefixFunctionIterationLemma)
={k:k<q–1andP
k+1P
q}
E
q–1consistsofthosevaluesofkЄΠ*[q–1]suchthatP
kcanbeextendedtoP
k+1
andgetapropersuffixofP
q.

67. References:
•ThomasHCormen.CharlesELeiserson,RonaldLRivest,CliffordStein,
IntroductiontoAlgorithms,ThirdEdition,TheMITPressCambridge,
MassachusettsLondon,England.