replace.cpp

数据结构编程---串的知识

//【例3.3】  替换子串。

#include "SString.h"                             //字符串类

int main() 
{
/*
    //BF
//    SString target("abbabaaba"), pattern("aba");
    SString target("aaaaaa"), pattern("aab");
//    cout<<target<<".indexOf('c')="<<target.indexOf('c')<<endl;
    cout<<target<<".indexOf("<<pattern<<")="<<target.indexOf(pattern)<<endl;


    //替换子串
    SString target("abbabaabaabac"), pattern("aba"), replacement("xy");
//    SString target("aaa"), pattern("a"), replacement("ab");
    cout<<"target="<<target<<endl;
    target.replace(pattern, replacement);
    cout<<"target.replace("<<pattern<<", "<<replacement<<"),   target="<<target<<endl;
    target.replaceAll(pattern, replacement);
    cout<<"target.replaceAll("<<pattern<<", "<<replacement<<"),   target="<<target<<endl;

    //删除子串
    SString target("abbabaabaxyabac"), pattern("aba");
//    SString target("aaa"), pattern("a");
    cout<<"target="<<target<<endl;
    target.remove(pattern);
    cout<<"target.remove("<<pattern<<"),  target="<<target<<endl;
    target.removeAll(pattern);
    cout<<"target.removeAll("<<pattern<<"),  target="<<target<<endl;
*/
    //KMP
    SString target="abdabcabbabcabc", pattern="abcabc";  //图3.11
//    SString target="aaaaaba", pattern="aab";                //最坏情况
    cout<<target<<".indexOf("<<pattern<<")="<<target.indexOf(pattern)<<endl;

    return 0;
}

/*
程序运行结果如下：
//BF
count=8
"abbabaaba".indexOf("aba")=3

count=12
"aaaaab".indexOf("aab")=3

count=12
"aaaaaa".indexOf("aab")=-1                       //最坏情况，比较m*(n-m+1)=12次，O(n*m)

count=3
"aaaaaa".indexOf("aaa")=0                        //最好情况，比较3次


//替换子串
target="abbabaabaabac"                         
target.replace("aba", "xy"),    target="abbxyabaabac"
target.replaceAll("aba", "xy"), target="abbxyxyxyc"
  
target="aaa"                         
target.replaceAll("a", "ab"),   target="ababab" 
  
//删除子串
target="abbabaabaxyabac"                         
target.remove("aba"),    target="abbabaxyabac"
target.removeAll("aba"), target="abbxyc"

//KMP
next[]:  -1 0 0 -1 0 0 
count=17
"abdabcabbabcabc".indexOf("abcabc")=9            //图4.11

next[]:  -1 -1 1 
count=9
"aaaaab".indexOf("aab")=3;                       //最坏情况，O(n+m)

*/

/*
KMP.indexOf("aabcbabcaabcaababc", "abcaababc")=9   //张乃孝书
nextk[]: -1 0 0 0 1 1 2 1 2 
next[]:  -1 0 0 -1 1 0 2 0 0 
KMP.count=20

KMP.indexOf("aaabaaaab", "aaaab")=4                //严蔚敏
nextk[]: -1 0 1 2 3 
next[]:  -1 -1 -1 -1 3 
KMP.count=9

KMP.indexOf("aabaaab", "aaab")=3
nextk[]: -1 0 1 2 
next[]:  -1 -1 -1 2 
KMP.count=7

KMP.indexOf("abbabaaba", "aba")=3                 //BF用例
nextk[]: -1 0 0 
next[]:  -1 0 -1 
KMP.count=6

*/