public kumar-abhishek /Cpp-snippets

Subversion checkout URL

You can clone with HTTPS or Subversion.

Fetching contributors…

Cannot retrieve contributors at this time

file 69 lines (63 sloc) 1.672 kb
 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 `/* * ===================================================================================== * * Filename: ZAlgorithm.cpp * * Description: Z Algorithm * * Version: 1.0 * Created: 03/07/2012 02:27:43 PM * Revision: none * Compiler: gcc * * Author: Kumar Abhishek (), kr.abhish@gmail.com * Company: * * ===================================================================================== */#include#include#include#includeusing namespace std;void computeZArray(vector &z,int n, string s){    z.push_back(0);//1st element is always zero    int L = 0, R = 0;    for (int i = 1; i < n; i++) {        if (i > R) {            L = R = i;            while (R < n && s[R-L] == s[R]) R++;            z.push_back(R-L); R--;        } else {            int k = i-L;            if (z[k] < R-i+1) z.push_back(z[k]);            else {                L = i;                while (R < n && s[R-L] == s[R]) R++;                z.push_back(R-L); R--;            }        }    }}int main(){    vector Z;    string text, pattern;    cin>>text>>pattern;    string concat = pattern + '\$' + text;    computeZArray(Z,concat.size(),concat);    /* cout<<"Z array" << endl; for(int i =0;i= pattern.size()){            found = true;            cout<<"found: "<
Something went wrong with that request. Please try again.