Re: [閒聊] 每日leetcode

[oin1104 (是oin的說)]

題目
家最少的字符
讓s變成回文


思路
把s翻轉之後
用hash記每一種前綴
然後用翻轉後的去找
有對上的話就代表可以是回文

但是這樣會炸記憶體
所以失敗


思路2
我用半個下午學了KMP
又機掰又詭異又複雜的演算法

一樣是翻轉之後
用原本的字串匹配翻轉後的字串
因為是從後面來 要注意一下
然後用KMP來找
找到底之後
還剩下的字符就是需要加上去的字符


太難了吧

幹





class Solution {
public:

    vector<int> next;
    int n ;

    void benext(string s)
    {
        int i = 0;
        int p = 1;

        while(p < n)
        {

            if(s[i] == s[p])
            {
                i++;
                next[p] = i;
                p++;

            }
            else if (i == 0)
            {
                next[p] = 0;
                p++;
            }
            else
            {
                i = next[i-1];
            }
        }
    }

    string shortestPalindrome(string s)
    {
        string rev = s ;
        reverse(rev.begin() , rev.end());
        n = s.size();
        next.resize(n,0);

        benext(s);

        int i = 0 ;
        int j = 0;



        while(i < n)
        {
            if(rev[i] == s[j])
            {
                i++;
                j++;
            }
            else if(j>0)
            {
                j = next[j-1];
            }
            else
            {
                i++;
            }

            if(j == n)break;
        }

        string res ;

        res = s;
        reverse(res.begin() , res.end());

        for( ; j < n ; j ++)
        {
            res.push_back(s[j]);
        }

        return res;

    }
};




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.162.42 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726833143.A.675.html
推 sustainer123: KMP又啥 怎麼那麼多奇怪的算法 哇哇嗚嗚嗚
→ oin1104: 我寫到想死
推 Furina: 大師
推 maitetsu: 回文就是y f ^x
→ oin1104: 小c 你的笑話是跟逼威力學來的嗎 超好笑的欸xd
推 mrsonic: 死了嗎
推 sixB: 差低
→ sixB: kmp很好玩ㄟ==
→ sixB: hash可以 On
→ sixB: suffix lca 好像也可以 還沒看懂
→ oin1104: hash記憶體會有點問題 我就試試看kmp了