Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

C++:
01 int pi(char* p, int*& A)
02 {
03     int cnt=0;
04     for(int i=0;p[i]!=;i++)
05         cnt++;
06     A=new int[cnt];
07     A[0]=0;
08     for(int i=1;i<cnt ;  ){
09         int j=i;
10         for(int t=0,k=0;(j<cnt)&&(p[j]==p[k]);j++,k++)
11             A[j]=k+1;
12         if(j<cnt)
13             A[j]=0;
14         i=j+1;
15     }
16     return cnt;
17 }
18 
19  char *strStr(char *haystack, char *needle) {
20         if((haystack==NULL)||(needle==NULL))
21             return NULL;
22         if(needle[0]==)
23             return haystack;
24         int start=-1;
25         int* M=NULL;
26         int n=pi(needle,M);
27         for(int i=;  ;  ){
28             for(int j=i,t=0;;j++,t++){
29                 if(needle[t]==){
30                    start=i;
31                    break;
32                 }
33                 if(haystack[j]!=needle[t]){
34                     i+=M[t]+1;
35                     break;
36                 }
37             }
38             if(start>=0)
39                 break;
40             if(haystack[i]==)
41                 break;
42         }
43         if(start<0)
44             return NULL;
45         int cnt=1;
46         for(int i=start;haystack[i]!=;i++)
47             cnt++;
48         char* A=new char[cnt];
49         int j=0;
50         for(int i=start;haystack[i]!=;i++,j++)
51             A[j]=haystack[i];
52         A[j]=;
53         return A;
54     }
Advertisements
This entry was posted in String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s