def build_index(docs):
    index = {}
    for doc_id, content in enumerate(docs):
        words = content.split()
        for word in words:
            if word not in index:
                index[word] = []
            index[word].append(doc_id)
    return index
 
# 使用示例
docs = ["hello world", "python is fun", "hello python"]
print(build_index(docs))
# 輸出：{'hello': [0, 2], 'world': [0], 'python': [1, 2], ...}

from collections import defaultdict
 
def build_optimized_index(docs):
    index = defaultdict(list)
    for doc_id, content in enumerate(docs):
        seen = set()
        words = content.split()
        for word in words:
            if word not in seen:
                seen.add(word)
                index[word].append(doc_id)
    # 對每個(gè)詞表排序
    for word in index:
        index[word].sort()
    return index
 
# 查詢優(yōu)化
def search(index, word):
    if word in index:
        return index[word]
    return []
 
# 使用二分查找優(yōu)化查詢
def binary_search(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low+high)//2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid +1
        else:
            high = mid -1
    return -1
 
# 示例：查找包含"python"的文檔
docs = ["hello world", "python is fun", "hello python", "python tutorial"]
index = build_optimized_index(docs)
print(search(index, "python"))  # 輸出 [1, 2, 3]

import bisect
from typing import List, Dict
 
class InvertedIndex:
    def __init__(self):
        self.index = {}  # 類型：Dict[str, List[int]]
        self.doc_counts = {}  # 類型：Dict[str, int]
 
    def add_document(self, doc_id: int, content: str):
        words = content.split()
        seen = set()
        for word in words:
            if word not in seen:
                seen.add(word)
                if word not in self.index:
                    self.index[word] = []
                    self.doc_counts[word] = 0
                # 使用bisect插入保持有序
                bisect.insort(self.index[word], doc_id)
                self.doc_counts[word] +=1
 
    def search(self, query: str) -> List[int]:
        if " AND " in query:
            terms = query.split(" AND ")
            results = self._search_single(terms[0])
            for term in terms[1:]:
                results = self._intersect(results, self._search_single(term))
            return results
        elif " OR " in query:
            terms = query.split(" OR ")
            results = []
            for term in terms:
                results = self._union(results, self._search_single(term))
            return results
        else:
            return self._search_single(query)
 
    def _search_single(self, term: str) -> List[int]:
        if term in self.index:
            return self.index[term]
        return []
 
    def _intersect(self, a: List[int], b: List[int]) -> List[int]:
        # 使用雙指針法求交集
        i = j = 0
        result = []
        while i < len(a) and j < len(b):
            if a[i] == b[j]:
                result.append(a[i])
                i +=1
                j +=1
            elif a[i] < b[j]:
                i +=1
            else:
                j +=1
        return result
 
    def _union(self, a: List[int], b: List[int]) -> List[int]:
        # 使用歸并法求并集
        result = []
        i = j = 0
        while i < len(a) and j < len(b):
            if a[i] == b[j]:
                result.append(a[i])
                i +=1
                j +=1
            elif a[i] < b[j]:
                result.append(a[i])
                i +=1
            else:
                result.append(b[j])
                j +=1
        result += a[i:]
        result += b[j:]
        return list(sorted(set(result)))  # 去重排序
 
# 使用示例
index = InvertedIndex()
docs = [
    "Python is great for data science",
    "Java is popular for enterprise applications",
    "JavaScript rules the web development",
    "Python and JavaScript are both scripting languages"
]
 
for doc_id, doc in enumerate(docs):
    index.add_document(doc_id, doc)
 
print(index.search("Python AND scripting"))  # 輸出 [3]
print(index.search("Python OR Java"))        # 輸出 [0,1,3]

class SimpleSearchEngine:
    def __init__(self):
        self.index = InvertedIndex()
        self.documents = []
 
    def add_document(self, content: str):
        doc_id = len(self.documents)
        self.documents.append(content)
        self.index.add_document(doc_id, content)
 
    def search(self, query: str) -> List[str]:
        doc_ids = self.index.search(query)
        return [self.documents[doc_id] for doc_id in doc_ids]
 
# 使用示例
engine = SimpleSearchEngine()
engine.add_document("Python is a versatile language")
engine.add_document("JavaScript dominates web development")
engine.add_document("Python and machine learning go hand in hand")
 
print(engine.search("Python AND machine"))  
# 輸出：['Python and machine learning go hand in hand']