1
2
3
1
2,
3
4
4,3
1
s =,a1,a2,a3,..,an”
s---- a1,a2,a3,..,an----
1a =,This is a string”
2b =,string
3c =,,
4d =,”
5e =,
1) 0;
2)
2
1;
c =,DATA STRUCTURE”f=“DATA” fc
2
t Ss T;
s=“ababcabcac”,t=“abc” T S3
3
3
1assign( s,t) t s
2 equal(s,t)
3) concat( s,t ) t s
4) lenght(s)
5) sub ( s,start,len,t)
0<=start<length(s) 0<=len<=length(s)-start
t s start,len,1,0
6index( s,t )
s t,s10
7 replace( s,t,v )
v s t
8 strcopy(s,t)
s t
9 empty( s )
10
10 ClearString( s )
s
11) StrInsert( s,start,t)
t s start
StrDelete( s,start,len)
s start len
C
#define MAX 255
char ch[MAX]
0 1 2 3 4 5 6 7 8 9 10 11 14… MAX-1
ch
,
char store[MAX];
int free ; */ */
3
…
#define MAX 100
Char t[MAX],s[MAX];
1 length(s)
int length(char s[ ])
{ int i;
for (i=0,s[ i]!=?\0?;i++);
return(i);
}
(2)
int sub(char s[ ],int start,int len,char t[ ])
{ int n,i;
n=length(s);
if (start <0 || start>=n )return (0);
if ( len<0 || len+start>n) return (0); //
for (i=0;i<len ;i++)
t[i]=s[start+i];
t[i]=?\0?;
return (1);
}
(3)
int concat( char s[ ],char t[ ])
{ int m,n,i;
m= length(s);
n=length(t);
if (m+n>=MAX) return(0);
for(i=0;i<n;i++) s[m+i]=t[i];
t[i]=?\0?;
return (1);
}
(4)
int equal( char s[ ],char t[ ])
{ int m,n,i;
m= length(s);
n=length(t);
if (m!=n) return(0);
for(i=0;i<m;i++) if (s[i]!=t[i])return(0);
return (1);
}
(1)
index(s,t,start) t
s=“abcdef”,t=“cde” index(s,t,0)=2,index( s,t,1)=2,
t=“ab” index( s,t,0)=0
t=“ad” index( s,t,0)=-1
(2) BF
s i ( i start) t t i,i 1 s i t
a b a b c a b c a c b a b
i=0
t = a b c a c Subch!=t
a b a b c a b c a c b a b
i=1
a b a b c a b c a c b a b
i=2
a b a b c a b c a c b a b
i=3
a b a b c a b c a c b a b
i=4
a b a b c a b c a c b a b
i=5
t = a b c a c
1
Subch!=tt = a b c a c
t = a b c a c Subch!=t
int index( char s[ ],char t[ ],int start )
{
,”,,
a b a b c a b c a c b a b
i=2
a b c
j=2
a b a b c a b c a c b a b
i=1
a
j=0
a b a b c a b c a c b a b
i=6
a b c a c
j=4
S[2]!=t[2],i=i- j+1,j=0
2
i=0
i=1
S[1]!=t[0],i=i- j+1,j=0
i=2
S[6]!=t[4],i=i- j+1,j=0
a b a b c a b c a c b a b
i=3
a
j=0
a b a b c a b c a c b a b
i=4
a
j=0
a b a b c a b c a c b a b
i=10
a b c a c j=5
2
S[3]!=t[0],i=i- j+1,j=0
S[4]!=t[0],i=i- j+1,j=0
j t,,i=i-n
i=4
i=3
i=5
int index1(char s[ ],char t[ ],int start )
{ // s startt -1
T
,”,,
s =,aaaaaaaaaaaaaaaba”
t =,aaaaaaaba”
3
D.E,Knuth,J.H.Morris,and V.R.Pratt.
a b c d a b a \0s
a b c \0t d a b c a c b
a b ct d a b
t =,t0t1tn,next( ),
0
}s u c h t h a t 0l a r g e s t |{
0.,,,,,,.,,,,,,,,,.,,,,,,,,,.,,,,,,,,,.,,,,,,,,,.,,,,,,,,,.,,,,,,,,,.,,,,,,,,,1
)( 110 jkjk ttttjkkM a x
j
jn e x t
0 1 2 10j 3 4 5 6 7 8 9
a b c \0t a b c a c a b
-1 0 0 \next 0 1 2 3 4 0 1
i
j
!
int Index_KMP ( char s[ ],char t[ ],int next[ ] )
{
int i = 0 ; j=0,m,n ;
m=strlen(s); n=strlen(t);
while ( i <m && j <n )
if (j==-1|| s[ i ]==t[ j ] ) { i++; j++; }
else j = next[ j ] ;
if ( j>=n) return ( i- n);
else return(-1);
}
i
j
next[j]
i
return
KMP
next [ j ]?
Method 1
0
}s u c h t h a t 0l a r g e s t |{
0.,,,,,,,,.,,,,,,,,,.,,,,,,,,,.,,,,,,,,,.,,,,,,,,,.,,,,,,,,,.,,,,,,,,,.,,,,,,,,,1
)( 110 jkjk ttttjkkM a x
j
jn e x t
Method 2
j?1
j
k=next ( j)
jjn e x t tt)(
yes
1)()1( jn e x tjn e x t
no
j
k = next ( j )
next (k ) =
next 2 ( j)
jjn e x t tt)(2
yes
1)()1( 2 jn e x tjn e x t
no…
next (k )-1
next[0]=-1
next[j]=k,
t0t1…t k-1”=“tj-k tj-k+1 … tj-1”
next[j+1],:
tk=tj
tk?tj
k-1
j?1
next ( j )-1
jnext ( j)
jjn e x t tt)(
yes
1)()1( jn e x tjn e x t
no
j
k = next ( j )
next (k ) =
next 2 ( j)
jjn e x t tt)(2
yes
1)()1( 2 jn e x tjn e x t
no…
next (k )-1
0
1)(
0 if1
)1( 1)1( jjne x tm ttmjn ex t
j
jn ex t m
void get_next ( char t[ ],int next[ ],int n)
{ int j,k;
j=0; k=-1; next[0]=-1;
while(j<n )
if (k==-1|| t[ j ]==t[ k ])
{ j++;k++; next[ j ]=k;}
else k=next [ k ];
}
0 1 2 10j 3 4 5 6 7 8 9
a b c \0t a b c a c a b
-1 0 0 \next 0 1 2 3 4 0 1
