f942 - 字串判斷

🔗 前往 ZeroJudge 原題

題目描述

題目要求在輸入的字串序列中找出第一個重複出現的字串，並輸出其第一次出現的索引和當前索引。輸入直到 EOF 結束。

解題思路

此題使用雜湊表 (Hash Table) 來解決。由於記憶體限制較嚴格，需要設計高效的雜湊函數。程式碼中使用了兩個雜湊函數 shash 和 sh2。shash 簡單地計算字串中所有字元的 ASCII 值的總和，而 sh2 則考慮了字元的位置，計算 (t[i] + i) % 31 的總和。使用兩個雜湊函數可以降低碰撞的機率。

程式碼使用兩個 map (雜湊表) mp 和 mp2 分別儲存 shash 和 sh2 的雜湊值以及對應的字串出現的索引。在讀取每個字串時，計算其兩個雜湊值，並檢查這兩個雜湊值是否已存在於 mp 和 mp2 中。如果都存在，則表示找到了重複的字串，輸出其索引並結束程式。如果不存在，則將該字串的雜湊值和索引儲存到 mp 和 mp2 中。

複雜度分析

• 時間複雜度: O(N * K)，其中 N 是字串的數量，K 是字串的平均長度。因為對於每個字串，都需要計算雜湊值和在雜湊表中查找。
• 空間複雜度: O(N * K)，最壞情況下，所有字串都不相同，需要儲存所有字串的雜湊值和索引。

程式碼

#include <iostream>
#include <map>
using namespace std;
map <int,int> mp,mp2;
string s;
int it;
int sh2(string t){
	int k=0;
	for(int i=0;i<t.length();++i){
		k+=(t[i]+i)%31;
	}
	return k;
}
int shash(string t){
	int k=0;
	for(int i=0;i<t.length();++i){
		k+=t[i];
	}
	return k;
}
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> s){
		++it;
		int tmp=shash(s),tmp2=sh2(s); 
		if(mp[tmp]&&mp2[tmp2]){
			cout << mp[tmp] << " " << it;
			break;
		}
		mp[tmp]=it;
		mp2[tmp2]=it;
	}
}