-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
122 lines (103 loc) · 3.1 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
<html>
<head>
<link rel="stylesheet" type="text/css" href="css/style.css">
<script type="text/javascript" src="js/jquery-1.11.1.js"></script>
</head>
<script type="text/javascript">
$(document).ready(function () {
$('#runButton').on('click', function () {
$('#prefix tr').remove()
$('#log li').remove()
var data = initPattern($('#pattern').val())
var indexes = indexArray(data.length)
$('#prefix').append(getRow("i", indexes))
$('#prefix').append(getRow("pattern", data))
var failureFunction = prefix($('#pattern').val())
$('#prefix').append(getRow("pi[i]", failureFunction))
})
});
/* This is prefix function or failure function according to original concept. Anyway whole magic is encapsulated here */
function prefix(s) {
var n = s.length;
var pattern = initPattern(s);
var pi = initArray(n);
var t = 0;
for (var i = 1; i < n; i++) {
showLogMessage("Now i :" + i);
while (t > 0 && isNotEqual(pattern[i], pattern[t])) {
showLogMessage("Going Back t = pi[t-1] t was " + t + " will be " + pi[t - 1]);// + " pattern[t] = " + pattern[pi[t-1]]);
t = pi[t - 1];
}
if (isEqual(pattern[i], pattern[t])) {
t++;
pi[i] = t;
showLogMessage("Incrementing pi[" + (i) + "]=" + t);
} else {
pi[i] = 0;
showLogMessage("Resetting pi[" + (i) + "]=0");
}
}
return pi;
}
/* Helper functions */
function showLogMessage(message) {
$('#log').append('<li>' + message + '</li>')
}
function initArray(n) {
var array = [];
for (var i = 0; i < n; i++) {
array.push(0);
}
return array;
}
function indexArray(n) {
var array = [];
for (var i = 0; i < n; i++) {
array.push(i);
}
return array;
}
function initPattern(s) {
var array = [];
for (var i = 0; i < s.length; i++) {
array.push(s.charAt(i));
}
return array;
}
function isEqual(a, b) {
console.dir("COMPARING " + a + "==" + b + " RESULT IS " + (a == b));
return a == b;
}
function isNotEqual(a, b) {
console.dir("COMPARING " + a + "!=" + b + " RESULT IS " + (a != b));
return a != b;
}
function getRow(rowLabel, data) {
var row = "<tr><td class='row-label'>" + rowLabel + ":</td>"
for (var i = 0; i < data.length; i++) {
row += "<td class='row-data'>" + data[i] + "</td>"
}
return row += "</tr>"
}
</script>
<body>
<br>
<table>
<tr>
<td>
<input type="text" id="pattern">
</td>
<td>
<button type="button" id="runButton">Calculate</button>
</td>
<br>
<div style="float: left;">
<table id="prefix">
</table>
</div>
<div>
<ul id="log">
</ul>
</div>
</body>
</html>