var BoyerMoore = function (pattern) { this.pattern = pattern; this.skip = this.buildSkip(pattern); this.next = this.buildNext(pattern); return this; } BoyerMoore.prototype.buildSkip = function (pattern) { var m = pattern.length; var skip = {}; for (var i = 0; i < m; i++) { skip[pattern[i]] = m - i - 1; } return skip; } BoyerMoore.prototype.buildNext = function (pattern) { var m = pattern.length; var g = []; for (var i = 0; i < m; i++) { g.push(m); } var next = []; for (var i = 0; i < m; i++) { next.push(2 * m - i - 1); } var j = m; for (var i = m - 1; i >= 0; i-- , j--) { g[i] = j; while (j < m && pattern[j] !== pattern[i]) { next[j] = Math.min(next[j], m - i - 1); j = g[j]; } } for (var i = 0; i < m; i++) { next[i] = Math.min(next[i], j + m - i) if (i >= j) { j = g[j]; } } return next; } BoyerMoore.prototype.match = function (text, pattern, skip, next) { pattern = pattern || this.pattern; skip = skip||this.skip; next = next || this.next; var n = text.length; var m = pattern.length; var count = 0; for (var i = m - 1; i < n;) { var j = m - 1; while (j >= 0 && text[i] == pattern[j]) { i--; j--; } if (j < 0) { count++; i += m + 1; } else { i += Math.max(skip[text[i]] || 0, next[j]); } } return count; } function Main(input) { var data = input.split("\n") var text = data[0]; var m = Number(data[1]); var total = 0; var i; for (i=0; i