問題文 http://poj.org/problem?id=2217Suffix Treeを実装したので最長共通部分文字列の問題にsubmit。 #include <iostream> #include <vector> #include <algorithm> #include <string> #include <cctype> using namespace std; const int SIZE = 128; struct Node { int b,e,d; //begin, end, distance f</cctype></string></algorithm></vector></iostream>…

文字列がいくつか与えられるので全ての文字列に現れる部分文字列の中で最長のものの長さを求めよ。 suffix arrayを使えば良い。共通部分文字列は蟻本に詳しく書いてる。嘘解法だった。隣同士の最長共通部分文字列しか計算してないのに通っていた。 #define I…

問題文 http://poj.org/problem?id=2217蟻本で解説されてる問題。蟻本と週刊spaghetti sourceさんを参考にしてローリングハッシュで実装してみた。TLEになった。答えも正しく出てるのかはわからない。 #include<iostream> #include<algorithm> #include<string> #include<vector> #include<cstdio> #define</cstdio></vector></string></algorithm></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6133.pdf補完機能を使って文字を打つとき、ひとつの文字を打つのに必要な最小の打たなければいけない文字数の平均を求めよ。 トライ木を使った。そのノードの子が2つ以上なら、そこまでで補完機能一…