🧵 String Matching Algorithm – Design and Analysis of Algorithms Project

This is my 4th semester project for the course Design and Analysis of Algorithms.
The task was to implement a string matching algorithm to identify complete "dish sets" from a sequence of given ingredients.

---

📌 Project Overview

The program reads:

• Groups → Sets of ingredients that define different dishes.
• Test cases → Lists of available ingredients.

It then determines whether all dishes can be prepared with the available ingredients, ensuring that each ingredient is only used once per dish.

---

⚙️ Algorithm Description

• Parsing Input: Reads data from a .txt file, storing groups and test cases.
• Sliding Window Search: Uses a moving window equal to the dish size to check for a complete match.
• Ingredient Removal: Once a dish is found, its ingredients are removed from the list to avoid reuse.
• Final Check: Returns True if all dishes are found in the given ingredients list, otherwise False.

This approach ensures no overlapping or repeated use of ingredients for multiple dishes.

---

🗂 File Structure

├── string.cpp # Main C++ implementation

├── p1_input.txt # Sample input file

├── p1_v2.txt # Additional test case set 1

├── p1_v3.txt # Additional test case set 2

├── p1_v22.txt # Additional test case set 3

---

🛠 Technologies Used

• C++ – Core language for implementation.
• File I/O – Reading groups and test cases from .txt files.
• Vectors & Strings – Storage and manipulation of ingredient data.

---

📄 Sample Input Format

Example from p1_input.txt:

groups = {{'lettuce', 'tomato', 'cucumber'}, {'pasta', 'tomato', 'chicken'}, {'flour', 'sugar', 'eggs', 'milk'}, {'milk', 'sugar', 'custard'}}

Test case 1

nums = ['onions', 'potatoes', 'pasta', 'lettuce', 'tomato', 'cucumber', ...]

---

📊 Sample Output

----- Test case 1 -----

Dishes: 4

Ingredients: 19

Outcome: True

🎯 Learning Outcomes

• Applied string matching logic to real-life analogy (dishes & ingredients).
• Implemented sliding window technique for efficient search.
• Improved skills in C++ file handling and vector manipulation.
• Practiced designing algorithm steps before coding.

📜 License

This project is for educational purposes only.