עצים בינארים

צביקה ברגר

רקורסיות

צביקה ברגר

מערכות הפעלה

​

התאמת מחרוזות

צביקה ברגר

בס"ד

Pattern Matching

בס"ד

FFT (Algo 1)

בס"ד

Abrahamson – Kosarahu (Algo 1)

בס"ד

Automa

בס"ד

Pattern: abbaba

a

b

a

b

a

b

b

a

a

b

a

b

a

b

Automa

בס"ד

Pattern: abbabc

a

b

a

b

c

b

b,c

a

a

b

a

b

a

b

c

a

c

c

c

c

• Size: O(m)
• Time
• O(m) building data structure
• O(n) traversing the text

​

• New improvements:
• Realtime
• Streaming

​

KMP 1972 (Knuth, Morris, Pratt)

בס"ד

a

b

a

b

c

b

T=abbaabbabb

KMP – Realtime

בס"ד

Karp-Rabin 1987

בס"ד

O(n+m)

Dictionary Problem

בס"ד

B

B

Automa

בס"ד

D={abab,baa}

a

b

b

a

b

a

a

a

b

a

a

a

b

b

b

b

T= a b a a b a a b a b

• Generalized version of KMP
• Composed of
• Goto function
• Failure function
• Report

​

• Space – O(size(D))
• Query time – O(|T|+ occ)

Aho Corasick 1975

בס"ד

D={aba,aabb,babb,bbaab}

Trie

בס"ד

a

b

a

a

b

b

b

b

b

b

a

a

a

b

Space=O(size(D))

T=ababb$

​

All Suffixes:�ababb$�babb$�abb$�bb$�b$�$

Indexing

בס"ד

0�1

2

3

4

5

Query: ab

T=ababb$

​

All Suffixes:�ababb$�babb$�abb$�bb$�b$�$

Suffix Tree

בס"ד

0�1

2

3

4

5

Query: ab

a

b

b

b$�[4,5]

b$

[4,5]

abb$

[3,5]

abb$�[2,5]

$

$

Compress Trie:

0

1

2

3

4

5

LCA

בס"ד

Text

Pattern

$

#

Build suffix tree for:

Harel & Tarjan 1983 “Fast algorithms for finding nearest common ancestors”: It is possible to preprocess a n-node tree in time O(n) and answer subsequent LCA queries in time O(1).

Suffix Tree + LCA

בס"ד

Suffix Tree + LCA

בס"ד

• Building suffix tree + LCA O(n+m) time
• Foreach text position O(k) time.
• Overall O(nk) time.

k-missmatches

בס"ד

k-missmatches

בס"ד

• Create suffix tree for: s = P#T

​

• Check P at each location i of T by kangrooing

​

Example:

​

P = A B A B A A B A C A B

T = A B B A C A B A B A B C A B B C A B C A …

i

k-missmatches

בס"ד

• Create suffix tree for: s = P#T

​

• Check P at each location i of T by kangrooing

​

Example:

​

P = A B A B A A B A C A B

T = A B B A C A B A B A B C A B B C A B C A …

i

k-missmatches

בס"ד

• Create suffix tree for: s = P#T

​

• Check P at each location i of T by kangrooing

​

Example:

​

P = A B A B A A B A C A B

T = A B B A C A B A B A B C A B B C A B C A …

i

k-missmatches

בס"ד

• Create suffix tree for: s = P#T

​

• Check P at each location i of T by kangrooing

​

Example:

​

P = A B A B A A B A C A B

T = A B B A C A B A B A B C A B B C A B C A …

i

k-missmatches

בס"ד

• Create suffix tree for: s = P#T

​

• Check P at each location i of T by kangrooing

​

Example:

​

P = A B A B A A B A C A B

T = A B B A C A B A B A B C A B B C A B C A …

i

k-missmatches

בס"ד

• Create suffix tree for: s = P#T

​

• Check P at each location i of T by kangrooing

​

Example:

​

P = A B A B A A B A C A B

T = A B B A C A B A B A B C A B B C A B C A …

i

k-missmatches

בס"ד

• Create suffix tree for: s = P#T

​

• Check P at each location i of T by kangrooing

​

Example:

​

P = A B A B A A B A C A B

T = A B B A C A B A B A B C A B B C A B C A …

i

k-missmatches

בס"ד

• Create suffix tree for: s = P#T

​

• Check P at each location i of T by kangrooing

​

Example:

​

P = A B A B A A B A C A B

T = A B B A C A B A B A B C A B B C A B C A …

i

Convulution

בס"ד

0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1

1 0 1 1 0 0 1

2

Convulution

בס"ד

0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1

1 0 1 1 0 0 1

2 3

Convulution

בס"ד

0 1 0 1 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 0 1

1 0 1 1 0 0 1

2 3 1

With FFT can be done in O(n log m) time

Counting missmatch with convulutions

בס"ד

T = a b c b a ⏀ b b a c a b b c

P = a b ⏀ b c a

T = 0 1 1 1 0 0 1 1 0 1 0 1 1 1

P = 1 0 0 0 0 1

a

T = 1 0 1 0 1 0 0 0 1 1 1 0 0 1

P = 0 1 0 1 0 0

b

T = 1 1 0 1 1 0 1 1 1 0 1 1 1 0

P = 0 0 0 0 1 0

c

Support wildcards

Counting missmatch with convulutions

בס"ד

T = a b c b a c b b a c a b b c

P = a b c b c a

T = 0 1 1 1 0 1 1 1 0 1 0 1 1 1

P = 1 0 0 0 0 1

a

T = 1 0 1 0 1 1 0 0 1 1 1 0 0 1

P = 0 1 0 1 0 0

b

T = 1 1 0 1 1 0 1 1 1 0 1 1 1 0

P = 0 0 1 0 1 0

c

Support wildcards

• If there are few places that match up to k:
• We can verify those possition using suffixtree and lca.
• How do we find those positions?
• What happen if we have many position which match up to k?

K-mismatch (ALP 2000) - Filter

בס"ד

• If there are few places that match up to k:
• We can verify those possition using suffixtree and lca.
• How do we find those positions?�If we have 2k or more different symbols in the pattern

​

K-mismatch (ALP 2000) - Filter

בס"ד

P = a b c b d c d a

k=2

F = a b c ⏀ d ⏀ ⏀ ⏀

If the distance of F to the text is bigger than k then the distance of the text to P bigger then k

F can match at most n/k times.

• If there are few places that match up to k:
• We can verify those possition using suffixtree and lca.
• How do we find those positions?�If we have 2k or more different symbols in the pattern

​

K-mismatch (ALP 2000) - Filter

בס"ד

P = a b c b d c d a

k=2

F = a b c ⏀ d ⏀ ⏀ ⏀

d

d

F

+1

• If there are few places that match up to k:
• We can verify those possition using suffixtree and lca.
• How do we find those positions?�If we have 2k or more different symbols in the pattern

​

K-mismatch (ALP 2000) - Filter

בס"ד

P = a b c b d c d a

k=2

F = a b c ⏀ d ⏀ ⏀ ⏀

a

a

F

+1

• If there are few places that match up to k:
• We can verify those possition using suffixtree and lca.
• How do we find those positions?�If we have 2k or more different symbols in the pattern

​

K-mismatch (ALP 2000) - Filter

בס"ד

P = a b c b d c d a

k=2

F = a b c ⏀ d ⏀ ⏀ ⏀

The total number of +1 is at most n

F can match at most n/k times.

Each position which have less then k missmatch should get at least k +1’a

K-mismatch (ALP 2000) - Filter

בס"ד

Wildcards

בס"ד

T = a b c b a ⏀ b b a c ⏀ b b c

P = a b ⏀ b c a

T = 00 01 10 01 00 ⏀⏀ 01 01 00 10 ⏀⏀ 01 01 10

P = 00 01 ⏀⏀ 01 10 00

a = 00

b = 01

c = 10

⏀= ⏀⏀

​

L2

בס"ד

L2

בס"ד

L2

בס"ד

נשים לב שאם יש התאמה יהיה 0 אחרת מספר חיובי.

L2

בס"ד

בכל איטרציה מורידים את האיבר הראשון ומוסיפים את האחרון

ב-O(1) (סך הכל O(n)).

L2

בס"ד

קונבולוציה

O(nlogm)

L2

בס"ד

חישוב קבוע (פעם אחת צריך לחשב)

O(m)

L2 matching with wildcards (Porat 2002)

בס"ד

במקום whildcard נשים 0:

L2 matching with wildcards (Porat 2002)

בס"ד

כדי לתקן נצטרך לחשב כמה נצטרך להוריד בכל היסט.

החישוב יהיה בצורה הבאה:

נכתוב בכל מקום שיש wildcard 1 ובכל מקום אחר 0,

בתבנית השנייה נכתוב את המרחקים בריבוע.

נחזור על תהליך זה כאשר הופכים בין הטקסט לתבנית.

חיבור שני התוצאות הוא הסכום שצריך להוריד.

​

בדוגמא שלנו קיבלנו 20 במקום 2, בתיקון קיבלנו 9+9=18.

לכן 20-18=2

L2 matching with wildcards (Porat 2002)

בס"ד

O(nlogm)

One Error

בס"ד

סיכום

בס"ד

LCA

בס"ד

בס"ד

Question 1

מועד א 2022

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 2

2009 מועד ב

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 3

2007 מועד ב

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 4

שאלות לדוגמא 2022

בס"ד

שאלות לדוגמא 2022

בס"ד

LCA

בס"ד

בס"ד

Question 5

2009 מועד א

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 6

2009 מועד א

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 7

2004 מועד א

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 8

תרגיל בית 2

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 9

תרגיל בית 2

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 9

תרגיל בית 2011 תרגיל 9

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 9

תרגיל בית 2011 תרגיל 12

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 9

תרגיל בית 2011 תרגיל 13

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 9

תרגיל בית 2011 תרגיל 10

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 9

תרגיל בית 2011 תרגיל 10

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

Question 9

תרגיל בית 2011 תרגיל 11

בס"ד

פתרון

בס"ד

LCA

בס"ד

בס"ד

שאלות?