C++ Program to Implement Knuth–Morris–Pratt Algorithm (KMP)

«
»
This C++ Program demonstrates the implementation of Knuth–Morris–Pratt Algorithm popularly known as KMP.

Here is source code of the C++ Program to implement Knuth–Morris–Pratt Algorithm (KMP). The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `/*`
2. ` * C++ Program to Implement Knuth–Morris–Pratt Algorithm (KMP)`
3. ` */`
4. `#include <iostream>`
5. `#include <cstring>`
6. `using namespace std;`
7. `void preKMP(string pattern, int f[])`
8. `{`
9. `    int m = pattern.length(), k;`
10. `    f[0] = -1;`
11. `    for (int i = 1; i < m; i++)`
12. `    {`
13. `        k = f[i - 1];`
14. `        while (k >= 0)`
15. `        {`
16. `            if (pattern[k] == pattern[i - 1])`
17. `                break;`
18. `            else`
19. `                k = f[k];`
20. `        }`
21. `        f[i] = k + 1;`
22. `    }`
23. `}`
24. ` `
25. `//check whether target string contains pattern `
26. `bool KMP(string pattern, string target)`
27. `{`
28. `    int m = pattern.length();`
29. `    int n = target.length();`
30. `    int f[m];     `
31. `    preKMP(pattern, f);     `
32. `    int i = 0;`
33. `    int k = 0;        `
34. `    while (i < n)`
35. `    {`
36. `        if (k == -1)`
37. `        {`
38. `            i++;`
39. `            k = 0;`
40. `        }`
41. `        else if (target[i] == pattern[k])`
42. `        {`
43. `            i++;`
44. `            k++;`
45. `            if (k == m)`
46. `                return 1;`
47. `        }`
48. `        else`
49. `            k = f[k];`
50. `    }`
51. `    return 0;`
52. `}`
53. ` `
54. `int main()`
55. `{`
56. `    string tar = "san and linux training";`
57. `    string pat = "lin";`
58. `    if (KMP(pat, tar))`
59. `        cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;`
60. `    else`
61. `        cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;`
62. `    pat = "sanfoundry";`
63. `    if (KMP(pat, tar))`
64. `        cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;`
65. `    else`
66. `        cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;`
67. `    return 0;`
68. `}`

```\$ g++ kmp.cpp
\$ a.out

'lin' found in string 'san and linux training'

------------------
(program exited with code: 1)