블록 체인 문자열

#include<iostream>

using namespace std;

const int BLOCK_SIZE = 4;

class Node
{
public:
    char data[BLOCK_SIZE];
    Node* next;
};

class KNode
{
    public:
    Node* node;
    int pos;
    int n;
    KNode()
    {
        node = NULL;
        pos = -2;
        n = -2;
    }
};

class LString
{
public:
    LString();
    ~LString();
    bool strAssign(const char *chars);
    int getLength();
    static int comp(LString &a, LString &b);
    void clear();
    static bool concat(LString &dest, LString &a, LString &b);
    bool sub(LString &dest, int pos, int len);
    int kmp(LString &str, int pos);
    void print();
    static void getNext(LString &a, KNode *nexts);
private:
    Node *head;
    Node *tail;
    int len;
};

LString :: LString()
{
    head = tail = new Node;
    head->next = NULL;
    len = 0;
    return;
}

LString :: ~LString()
{
    clear();
    delete head;
}

//    
void LString :: clear()
{
    while(head->next != NULL)
    {
        Node *p = head->next;
        head->next = p->next;
        delete p;
    }
    len = 0;
    tail = head;
}

void LString :: print()
{
    Node *p = head->next;
    int count = len;
    while( NULL != p)
    {
        for(int i = 0; i < BLOCK_SIZE && count; ++i,--count)
        {
            cout.put(p->data[i]);
        }
        p = p->next;
    }
    cout << endl;
}

bool LString :: strAssign(const char *chars)
{
    clear();
    //          ？      strlen？？？
    //     ，             ，          。
    int tLen = 0;
    const char *c = chars;
    while(*c)
    {
        tLen++;
        c++;
    }
    int count = 0;
    //      ，  ， SIZE   ，         
    Node *p;
    for(int i = 0; i < tLen; ++i,count = (count + 1)%BLOCK_SIZE)
    {
        if(count == 0)
        {
            p = new Node;
            tail->next = p;
            p->next = NULL;
            tail = p;
        }
        p->data[i % BLOCK_SIZE] = chars[i];
    }
    len = tLen;
    return true;
}

int LString :: getLength()
{
    return len;
}

//     。
bool LString :: concat(LString &dest, LString &a, LString &b)
{
    if(&dest == &a)
    {

        int counta = a.len % BLOCK_SIZE;
        Node *pb = b.head;
        int ia = counta,ib = 0,countb = 0;
        while(countb < b.len)
        {
            if(ia == 0)
            {
                //       ，             
                Node *p = new Node;
                a.tail->next = p;
                p->next = NULL;
                a.tail = p;
            }
            if(ib == 0)
            {
                pb = pb->next;
            }
            a.tail->data[ia] = pb->data[ib];
            //i           ，count       ，    
            ia = (ia + 1)%BLOCK_SIZE;
            ib = (ib + 1)%BLOCK_SIZE;
            countb++;
            a.len++;
        }
    }
    else
    {
        char *s = new char[a.len + b.len];
        int count = 0,i = 0,tLen = a.len,index = 0;
        Node* p = a.head;
        //            a  b   
        for(int k = 0; k < 2; ++k)
        {
            while(count < tLen)
            {
                if(i == 0)
                {
                    p = p->next;
                }
                s[index++] = p->data[i];
                i = (i + 1) % BLOCK_SIZE;
                count++;
            }
            p = b.head;
            count = 0;
            i = 0;
            tLen = b.len;
        }
        //             dest，   assign  。
        dest.clear();
        p = dest.head;
        while(count < index)
        {
            if(i == 0)
            {
                p = new Node;
                dest.tail->next = p;
                p->next = NULL;
                dest.tail = p;
            }
            dest.tail->data[i] = s[count];
            count++;
            i = (i + 1) % BLOCK_SIZE;
        }
        dest.len = index;
        delete []s;
        return true;
    }
}

//              。          ，     
//   BLOCK_SIZE              
int LString :: comp(LString &a, LString &b)
{
    int i = 0,count = 0;
    Node *pa = a.head;
    Node *pb = b.head;
    while(i < a.len && i < b.len)
    {int kmp(LString &str, int pos);
        if(count == 0)
        {
            pa = pa->next;
            pb = pb->next;
        }
        if(pa->data[count] != pb->data[count])
        {
            return (pa->data[count] - pb->data[count]);
        }
        else
        {
            count = (count + 1) % BLOCK_SIZE;
            i++;
        }
    }
    if(a.len == b.len)
    {
        return 0;
    }
    else
    {
        return (a.len - b.len);
    }
}

bool LString :: sub(LString &dest, int pos, int lens)
{
    if(pos < 0 || pos >= lens || lens < 0)
    {
        cout << "Arguments Error!" << endl;
        return false;
    }
    int count = 0;
    int i = pos % BLOCK_SIZE;
    int j = pos / BLOCK_SIZE;
    //                   
    int length = lens;
    if(lens + pos > len)
    {
        length = len - pos;
    }
    char *s = new char[length];
    Node *p = head->next;
    for(int k = 1; k <= j; ++k)
    {
        p = p->next;
    }

    while(count < length)
    {
        s[count] = p->data[i];
        i = (i+1) % BLOCK_SIZE;
        //       ，     ，    ，len = 8        
        if(i == 0)
        {
            p = p->next;
        }
        ++count;
    }
    //              
    dest.clear();
    p = dest.head;
    count = 0,i = 0;
    while(count < length)
    {
        if(i == 0)
        {
            p = new Node;
            dest.tail->next = p;
            p->next = NULL;
            dest.tail = p;
        }
        dest.tail->data[i] = s[count];
        count++;
        i = (i + 1) % BLOCK_SIZE;
    }
    dest.len = length;
    delete []s;
    return true;
}

//        ，             
//     ，          i，     3       
//  ，       i，       ，               
//         KMP     
void LString :: getNext(LString &str, KNode *nexts)
{
    nexts[0].n = -1;
    nexts[0].node = str.head;
    nexts[0].pos = -1;
    int counta = 0,ia = 0;
    int countb = -1,ib = -1;
    Node *pa = str.head->next;
    Node *pb = str.head;

    while(counta < str.len - 1)
    {
        if(countb == -1 || (pa->data[ia] == pb->data[ib]))
        {
            ++counta;
            ++countb;
            ia = (ia + 1) % BLOCK_SIZE;
            ib = (ib + 1) % BLOCK_SIZE;
            if(ia == 0)
            {
                pa = pa->next;
            }
            if(ib == 0)
            {
                pb = pb->next;
            }

            if(pa->data[ia] == pb->data[ib])
            {
                nexts[counta].n = nexts[countb].n;
                nexts[counta].pos = nexts[countb].pos;
                nexts[counta].node = nexts[countb].node;
            }
            else
            {
                nexts[counta].n = countb;
                nexts[counta].pos = ib;
                nexts[counta].node = pb;
            }
        }
        else
        {
            ib = nexts[countb].pos;
            pb = nexts[countb].node;
            countb = nexts[countb].n;
        }
    }

}

int LString :: kmp(LString &str, int pos)
{
    KNode *nextss = new KNode[str.len];
    LString :: getNext(str, nextss);
    int counta = pos % BLOCK_SIZE,ia = 0;
    int countb = 0,ib = 0;
    Node *pa = head->next;
    Node *pb = str.head->next;
    int j = pos / BLOCK_SIZE;
    for(int k = 1; k <= j; ++k)
    {
        pa = pa->next;
    }

    while(counta < len && countb < str.len)
    {
        if(pa->data[ia] == pb->data[ib])
        {
            ia = (ia + 1) % BLOCK_SIZE;
            ib = (ib + 1) % BLOCK_SIZE;
            counta++;
            countb++;
            if(ia == 0)
            {
                pa = pa->next;
            }
            if(ib == 0)
            {
                pb = pb->next;
            }
        }
        else
        {

            ib = nextss[countb].pos;
            pb = nextss[countb].node;
            countb = nextss[countb].n;

            if(countb == -1)
            {
                ia = (ia + 1) % BLOCK_SIZE;
                if(ia == 0)
                {
                    pa = pa->next;
                }
                 counta++;
                 pb = str.head->next;
                 ib = 0;
                 countb = 0;
            }
        }
    }

    if(countb >= str.len)
    {
        delete []nextss;
        return (counta - countb);
    }
    else
    {
        delete []nextss;
        return -1;
    }

}

int main()
{
    LString myStringA,myStringB,myStringC;
    myStringA.strAssign("Hello,Wo");
    myStringB.strAssign("NONO");
    int resu = LString :: comp(myStringA, myStringB);
    cout << resu << endl;
    myStringA.print();
    LString :: concat(myStringA, myStringA, myStringB);
    myStringA.print();
    cout << myStringA.getLength() << endl;
    myStringA.sub(myStringC, 4, 10);
    myStringC.print();
    myStringB.print();
    int pos = myStringA.kmp(myStringB, 0);
    cout << "Pos:" << pos << endl;
    return 0;
}