Information Technology Reference
In-Depth Information
h e pseudocode of this two-phase linear time algorithm is presented as follows:
NS Algorithm 2: Dynamic programming approach
∊
≤
≤
=
∊
Input:
l
,
r
,
t
N
where 1
r
l
,
t
o(r) and s
S and ˆ denotes
⊂
string s stripped of leftmost bit, and
S
U
Output:
Array
C
[
s
] number of unmatched strings by any string in S,
where the strings are examined from left to right
Phase I: Solving the counting recurrence
1
begin
2
for
1
≤
i
≤
l
−
r
+
1
≤
3
while
|
C
i
[
s
]
|
|
t
|
do
4
if
t
i,s
matches with any bit string of S
then
=
5
C
i
[
s
] :
0
6
else
=
⋅
+
⋅
7
C
i
[
s
] :
C
i
+
1
[ˆ
0]
C
i
+
1
[ˆ
1]
8
endwhile
9
endfor
10
end
Phase II: Generating strings unmatched by S
1
begin
∑
2
Total number of unmatched by S:
T
C
1
[]
s
, where
C
1
[
s
]
sS
∈
denotes the number of unmatched
l
-bit string
3
If
k
∊
{1,2, …,
T
}
then
4 the
k
th matched string
u
k
is determined from steps 5 to 11
5 First interval (
P
1
,
Q
1
] is calculated as
∑
∑
P
c
[]
s
k
Q c
[]
s
1
1
1
1
ss
ss
1
1
6 Subsequent intervals (
P
i
, Q
i
] are calculated as from steps 7 to 10
7
for
i
=
2, …, (
l
−
r
+
1)
P
,
if
, if
b
0
i
1
i
1
8
P
i
Pc
[
s
0
]
b
1
i
1
i
i
1
i
1
Pc
[
s
0
]
, f
b
0
1
i
1
i
i
1
i
1
9
Q
i
Q
,
if
b
i
1
i
1
10
endfor
11
endif
12
end
Search WWH ::
Custom Search