z-algorithm

1.0.1 • Public • Published

Z algorithm (Linear time pattern searching Algorithm)

This algorithm finds all occurrences of a pattern in a text in linear time. Let length of text be n and of pattern be m, then total time taken is O(m + n) with linear space complexity.

The algorithm runs in linear time because we never compare character less than R and with matching we increase R by one so there are at most T comparisons. In mismatch case, mismatch happen only once for each i (because of which R stops), that’s another at most T comparison making overall linear complexity.

Install

 
npm install z-algorithm --save
 
or 
 
yarn install z-algorithm
 

Running the tests

you need to install jest

 
npm test
 
or 
 
yarn test
 

Usage

 
import z from 'z-algorithm';
 
let result = z.search('Hello World', 'Hello'); 
 

Examples

 
import z from 'z-algorithm';
        
let result = z.search('Hello World', 'Hello'); 
// result = [0]
 
let result = z.search('Google', 'o'); 
// result = [1,2]
 
let result = z.search('karimation', 'i'); 
// result = [3,7]   
 

Author

kerim selmi karimation

License

This project is licensed under the MIT License

Package Sidebar

Install

npm i z-algorithm

Weekly Downloads

22

Version

1.0.1

License

MIT

Unpacked Size

4.89 MB

Total Files

6

Last publish

Collaborators

  • selmi-karim