→ bleed1979:突然發現replace和original變數取名取反了。 03/21 10:26
稍微修改一下KMP Algorithm，做到幾近即時讀寫。
KMP Algorithm
http://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080
修改一個地方就是下面程式碼註解掉的地方。
原本是更新前綴的index，但修改成歸零。
不知道有沒有critical的pattern，程式碼有錯請提出來，我再做修正。
KMP.in
==========================================
aaaaaa aaaaaa
aa aa
aaabbb bbbbbb
bababa bababa
cad cadaaa
==========================================
KMP.cpp
==========================================
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
void preKmp(const string &x, int m, vector<int> &kmpNext)
{
int i, j;
i = 0;
j = kmpNext[0] = -1;
while (i < m)
{
while (j > -1 && x[i] != x[j])
j = kmpNext[j];
++i;
++j;
if (x[i] == x[j])
kmpNext[i] = kmpNext[j];
else
kmpNext[i] = j;
}
}
void KMP(ostream &fout, ifstream &fin,
const string &x, int m, const string &y, int n)
{
vector<int> kmpNext(m + 1);
/* Preprocessing */
preKmp(x, m, kmpNext);
/* Searching */
int i = 0;
char c = ' '; // any character
while (!fin.eof())
{
while (!fin.eof() && i > -1 && x[i] != (c = fin.get()))
{
if (kmpNext[i] == -1 && i)
fout << x.substr(0, i);
i = kmpNext[i];
}
++i;
if (i >= m)
{
//i = kmpNext[i];
i = 0;
fout << y;
}
else
{
if (!fin.eof() && i == 0)
fout.put(c);
}
}
}
int main()
{
ofstream fout ("KMP.out");
ifstream fin ("KMP.in");
const string replace("aaa"), original("bbb");
KMP(fout, fin, replace, replace.length(), original, original.length());
fout.close();
fin.close();
return(0);
}
==========================================
Bleed
※ 引述《kimgtob (K.L)》之銘言：
: 抱歉今天發了很多次文章
: 也問過同學了@_@，不過有些地方還是不懂
: 題目大意 將一文字檔內的連續3個a 換成 bbb
: 例 aa aa
: aaabbb bbbbbb
: bababa bababa
: cad cad
:
: 卡在下面的for處 以及n的部分 還有while 中間如何取代的地方
: 他的for 放在while 外面 那跟n 與a的修改有關嗎?
: #include<iostream>
: #include<fstream>
: using namespace std;
: using std::cout;
: int main ()
: {
: ifstream Input;
: ofstream Output;
: int n=0;
: char ch;
: Output.open("output.txt");
: Input.open("inpit.txt");
: if(!Input)
: {
: Output<<"檔案開啟失敗";
: return 0;
: }
: while (Input.get(ch))
: {
: 這邊我想請問一下
: 要如何做到 邊讀邊修改這個動作?
: 它不是一個字一個字讀進去嗎?
: 我用一個counter去數
: 數到第三個時 要修改的話
: 有辦法往後退三個字元再換成b嗎?
: }
: // for (int i=0; i<n; i++)
: // Output<<'a';
: Input.close();
: Output.close();
: return 0;
: }
: 謝謝各位 ! 如有違反版歸自刪
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97