机试第4章

string常用操作

s.insert(idx, str);
s.erase(begin, end); // 删除[begin, end)
s.clear();
s.substr(idx, len); // 起始位置，长度

if (s.find(str) != string::npos)

浮点数加法（类似大数加法）

string add(string s1, string s2)
{
    string int1 = s1.substr(0, s1.find('.')), int2 = s2.substr(0, s2.find('.'));
    string frac1 = s1.substr(s1.find('.') + 1), frac2 = s2.substr(s2.find('.') + 1);

    if (int1.size() < int2.size())
        int1 = string(int2.size() - int1.size(), '0') + int1;
    else
        int2 = string(int1.size() - int2.size(), '0') + int2;
    if (frac1.size() < frac2.size())
        frac1 = frac1 + string(frac2.size() - frac1.size(), ' ');
    else
        frac2 = frac2 + string(frac1.size() - frac2.size(), ' ');

    int carry = 0;
    string fraction = string(frac1.size(), ' ');
    for (int i = fraction.size() - 1; i >= 0; --i)
    {
        int cur = frac1[i] - '0' + frac2[i] - '0' + carry;
        carry = cur / 10;
        fraction[i] = cur % 10 + '0';
    }
    string integer = string(int1.size(), ' ');
    for (int i = integer.size() - 1; i >= 0; --i)
    {
        int cur = int1[i] - '0' + int2[i] - '0' + carry;
        carry = cur / 10;
        integer[i] = cur % 10 + '0';
    }
    if (carry == 1)
        return '1' + integer + '.' + fraction;
    else
        return integer + '.' + fraction;
}

kmp算法

const int MAXN = 1e6 + 5;
const int MAXM = 1e3 + 5;
char s[MAXN], t[MAXM];
int nxt[MAXM];

void getnxt(int m)
{
    nxt[0] = -1;
    int i = 0, j = -1;
    while (i < m)
        if (j == -1 || t[i] == t[j])
            nxt[++i] = ++j;
        else
            j = nxt[j];
}

int kmp(int n, int m)
{
    getnxt(m);
    int i = 0, j = 0;
    while (i < n)
        if (j == -1 || s[i] == t[j])
        {
            i++, j++;
            if (j == m)
                return i - m + 1;
        }
        else
            j = nxt[j];
    return -1;
}