FilesExpand file tree

 master

/

KMP.js

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

38 lines (35 loc) · 807 Bytes

 master

/

KMP.js

Top

File metadata and controls

• Code
• Blame

38 lines (35 loc) · 807 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

let kmp = function (origin, keyword) {

let oDump = origin.split("");

let kDump = keyword.split("");

let oLength = origin.length;

let kLength = keyword.length;

let failure = [];

failure.length = kDump.length;

failure.fill(-1);

// failure 배열 세팅

for (let i = 1; i < kLength; i++) {

let idx = 1 + failure[i - 1];

if (kDump[i] === kDump[idx]) {

failure[i] = idx;

} else {

failure[i] = -1;

}

}

// 비교 시작

let n = 0,

m = 0;

while (m < kLength && n < oLength) {

if (oDump[n] === kDump[m]) {

n++;

m++;

} else if (m === 0) {

n++;

} else {

m = 1 + failure[m - 1];

}

}

console.log(m, kLength);

console.log(n, kLength);

return m === kLength ? n - kLength : -1;

};

console.log(kmp("abcdef", "a"));