SCU 4438 Centor(審査員)(KMPアルゴリズムと模擬スタックの応用𞓜HASH表と模擬スタックの結合)

6010 ワード

KMPアルゴリズムデータ構造-スタック

Center
froog is now a editor to censor so-caled sensitive words(敏感語)
She has a long text pp.Her job is relatively simple--just to find the first occurence of sensitive word ww and remove it.
froog repeat over and over again.Help her do the tedious work.
フレッグは現在編集員で、いわゆる河蟹語を専門に審査しています.
彼は今長いテキストpを持っています.彼の仕事は比較的簡単です.
フレッグは何度も繰り返して、彼にこのつまらない任務を完成させるように手伝います.
Input
The input consists of multile tests.For each test:
複数のグループのデータを含むグループを入力します.
The first line contains 11 ストリングス ww.The second line contains 11 ストリングス pp.
最初の行は文字列Wを含み、2行目は文字列Pを含む.
(1≦length of w、p≦5⋅1061≦length of w、p≦5⋅106、 w,pw,p consists of only lowercase letter)
Output
For each test,write 11 string which denotes the censored text.
テストサンプルごとに文字列を出力します.河蟹になったテキストを表します.
Sample Input

    abc
    aaabcbc
    b
    bbb
    abc
    ab

Sample Output

    a
    
    ab

この問題を見たばかりの時は、テキストを削除した後のテキストは前に従って削除テキストの位置に移動します.Pythonのダイナミックメモリ管理に似ています.最初の考えはkmp+vectorですが、SCUOJで1986 msの高評価を得ました.
Caution:本題のデータが小さいので、stingタイプとcin、cout、stl-stack(純C時間200~400 ms、C with STL and iostream時間1000~140 ms、時間制限1500 ms)を慎重に使う
KMP+アナログスタック
プログラムの実現にはテキストを中断する必要がありますので、キーワードを削除する目的を達成しました.スタックというデータ構造はちょうど私達の要求を満たすことができます.kmpアルゴリズムで対応する文字列にマッチしながら、元の文字列を徐々にスタックに押し込みます.マッチングしたら、マッチングした文字列を全体的にスタックから引っ張り出して、「削除」の効果を実現しました.マッチングは成功文字列の最後尾の文字にマッチしてから続けられますので、このプロセスは「自動接続」を満足させます.の効果です
考えを簡単に述べる

まず、KMPアルゴリズムを実行するために必要なNEXT配列をある個々のモジュール「生産」によって完成させなければなりません.このプロセスは本質的にKEYWORD文字列が自分に対するマッチ(match)であり、NEXT配列の役割はあるマッチング失敗後にKEYWORDの属するポインタが文字列のどの位置に戻るかです.

は、TEXT文字列の文字を1サイクルごとにスタックに押し込み、その後、スタック内のすべての文字にKMPアルゴリズムを実行し、マッチングに成功すると、このサブ文字列をスタックから追放する(アナログポインタからサブ文字列の長さを減算する).

スタックに残っている文字が答えです.

詳細はコードを参照してください

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define DETERMINATION main
#define lldin(a) scanf("%lld",&a)
#define din(a) scanf("%d",&a)
#define printlnlld(a) printf("%lld
",a)
#define printlnd(a) printf("%d
",a)
#define printlld(a) printf("%lld",a)
#define printd(a) printf("%d",a)
#define reset(a,b) memset(a,b,sizeof(a))
const int INF=0x3f3f3f3f;
using namespace std;
const double PI=acos(-1);
typedef long long ll;
typedef long double ld;
const int mod=1000000007;
///Schlacht von Stalingrad
/**Although there will be many obstructs ahead,
the desire for victory still fills you with determination..**/
char text[7650000],key[7650000];
int next2[7650000],tmp[7650000];
ll indice;//      
char impersonated[7650000];//   
void generator()//next      ，                  
    （          ）            。     
{
    ll ph=-1,pt=0;
    next2[0]=-1;
    ll klen=strlen(key);
    while(pt0&&key[pk]!=text[pt])
            pk=next2[pk];//     
        if(key[pk]==text[pt])
            pk++;//  
        tmp[indice]=pk;//              ，     next      .
       // cout<

HASH表+アナログスタック
私達はすべてhash表がKEY-VALE類のデータ構造であることを知っています.キーの値を把握すれば、私達はこのキーの指す内容にアクセスできます.対応してキーの値が間違っていたら、私達は自然に正しい内容にアクセスできません.
大体次の通りです.

使いやすいHASH数を定義して暗号化します.文字列

KEYWORDのHASH値

を求めます.

TEXTの文字を循環的にアナログスタックに押し込んで、スタック内のKEYWORD長さのhash値を求めることにより、STACK[CURRENT-LOCATION]-(STACK[CURRENT-KEYWOR.SIZE.)*HAZSHORI[24].

は、求められたHASH値がKEYWORDのHASH値に等しいかどうかを判断し、もしそうであれば、スタックポインタを下に移動する(この文字列を削除する).

出力スタックの底から針に至る要素

コードは以下の通りです

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define DETERMINATION main
#define lldin(a) scanf("%lld",&a)
#define din(a) scanf("%d",&a)
#define printlnlld(a) printf("%lld
",a)
#define printlnd(a) printf("%d
",a)
#define printlld(a) printf("%lld",a)
#define printd(a) printf("%d",a)
#define reset(a,b) memset(a,b,sizeof(a))
const int INF=0x3f3f3f3f;
using namespace std;
const double PI=acos(-1);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod=1000000007;
const int tool_const=1999112620000907;
const int tool_const2=33;
///Schlacht von Stalingrad
/**Although there will be many obstructs ahead,
the desire for victory still fills you with determination..**/
char text[6000000],keyword[6000000];
ull hash_array[6000000],hash_of_text[5050000];
char forging_stack[5050000];
void readiness()
/*         HASH    ，  judge         HASH   ，
              HASH ，               HASH      。
*/
{
    hash_array[0]=1;
    for(int i=1;i<=500007;i++)
        hash_array[i]=hash_array[i-1]*tool_const2;
}
bool judge(ll current,ll klen,ll hashvalue)
{
    if(hash_of_text[current]-hash_of_text[current-klen]*hash_array[klen]==hashvalue)
         return true;
    else
        return false;
}
int DETERMINATION()
{
    readiness();
    while(~scanf("%s %s",keyword,text))
    {
        ull klen=strlen(keyword);
        ull tlen=strlen(text);
        ull khash=0;
        for(int i=0;i=klen&&judge(top_pointer,klen,khash))
                {
                    //cout<

poj 3494 dp+単調スタック