一样用flagA=0, flagB=0开始
flagC = 0代表目前在C里面验证的字符位置,令A[],B[],C[]为分别三个string
基本精神为,从flagC开始一一把C往后分别跟A,B的字串进行比对，分别把与C相同的字符数存入sameLengthA sameLengthB，如果:
1.sameLengthA, sameLengthB有任何一者比较长 那就代表此段取sameLength长度较长字串的片段(因为如果取较短的一定错), Ex:
sameLengthA=1,sameLengthB=3就把flagC+=sameLengthB, flagB+=sameLengthB
2.sameLengthA, sameLengthB相同:
出现这种状况 只有以下两种可能:
(i)flagA+sameLengthA+1==A字串长度或者flagB+sameLengthB=B字串长度 简单来说 就是其中一者已经读到尾巴了
(ii)C不是A,B交错而成，原因如下:
因为(i)已经排除了AB读完的状况 所以AB后面必有字符
如果A[flagA+sameLengthA+1]=/=B[flagB+sameLengthB+1]
则代表不管是A[flagA+sameLengthA+1]还是B[flagB+sameLengthB+1]都不是C[flagC+sameLengthA+1] 所以C不是AB交错而成
如果A[flagA+sameLengthA+1]==B[flagB+sameLengthB+1]
则代表A[flagA+sameLengthA+1]==B[flagB+sameLengthB+1]都不等于C[flagC+sameLengthA+1] 所以C不是AB交错而成
implementation:
bool checkinterleave(char A[],char B[], char C[]){//returns true when C is interleaved by A,b;else return false
int flagA;int flagB;int flagC;
int tA;int tB; int tC;
int sameLengthA;int sameLengthB;
tA=tB=tC=flagA=flagB=flagC=0;
int lenA=strlen(&A[0]);int lenB=strlen(&B[0]);int lenC=strlen(&C[0]);
while(flagC<lenC){
//find sameLengthA
sameLengthA=0;
tA=flagA;
tC=flagC;
while((tA<lenA)&&(A[tA]==C[tC])){
sameLengthA++;
tA++;
tC++;
}
//find sameLengthB
sameLengthB=0;
tB=flagB;
tC=flagC;
while((tB<lenB)&&(A[tB]==C[tC])){
sameLengthB++;
tB++;
tC++;
}
if(sameLengthA==sameLengthB){
return false;
}else{
if(sameLengthA>sameLengthB){
flagC+=sameLengthA;
flagB+=sameLengthB;
}else{
flagC+=sameLengthA;
flagA+=sameLengthA;
}
if((flagC==lenC)&&(flagB==lenB)&&(flagA==lenC)){
return true;
}
}
}
}
不知道这样行不行?

先不论对错, 你这是 O(n^2) 吧...再者 A = B = "abc" C = "abcabc" 好像是反例或者如果你觉得这个 C 太扯 那 "abacbc" 也可以唔, 实际跑你这段程式, 最简单的 abc def adbecf 就炸了 XD

我不懂为什么会是O(n^2)? C的每个字符只针对A,B个比对一一次 之后是直接加上去

嗯, 仔细想想后应该是线性没错, 不过正确性就...ok, 这程式码里有些打错字的地方, 但即使修过后abc abc abcabc 跟 abc abc abacbc 都回传 false更夸张一点的例包含 aaa aaa aaaaaa 也是你的算法的反例