P1 打倒怪獸 - Defeat the monster

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.1 kB
0
Indexable
Never
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
using std::string;

string n, m; //n:大摩導師的咒語,m:書的內容
int p=0, N; //判斷有無符合資料的(用來輸出not found)
int dic[1000000];//記憶相似字串的開頭,用來排序 

bool cmp(int i, int j)
{
	for(int k = 0; k < N; ++k)
		if(m[i+k] != m[j+k])
			return m[i+k] < m[j+k];
	return true;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    N=n.size();   
    for(int i=0; i<m.size(); ++i){
        int f=0; //記錯誤次數
        for(int j=0; j< N; ++j){
            if(f>1) break; //錯誤1次以上,跳出
            if(n[j] != m[i+j]) ++f; //有錯
            if(j==n.size()-1&&f<=1){ //咒語符合
                dic[p] = i;
				++p;
            }
        }
    }
    if(p==0){
        cout <<"Not found\n";
        return 0;
    }
    
    sort(dic, dic+p, cmp);
    for(int i=0; i<p; ++i)
	{
		for(int j = 0; j < N; ++j)
			cout << m[dic[i]+j];
		cout << "\n";
	}
}