Firsthw.cpp

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <fstream>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;

bool DFS(int index, string line, char start, vector<char> ends, vector<vector<vector<char>>> table, vector<vector<char>> linelist) {
    if(index == line.length()) {
        for(char c : ends) {
            if(c == start) return true; 
        }
        return false;
    }

    char cur_char = line[index];
    int state_index = start - '0';
    int char_index = cur_char - '0';

    //цикл поиска по листу направлений,потом по таблице и там уже както через dfs подобный алгоритм
    if(state_index < table.size() && char_index < table[state_index].size()) {
        for(char state : table[state_index][char_index]) {
            //от строки берем индекс а не отрезаем на каждой итерации прибавляем, смотрим
            //для всех состояний соседних
            if(DFS(index+1, line, state, ends, table, linelist)) return true;
            
        }
    } 
    return false;
    
}

int main() {
    string filename = "automaton.txt";
    std::ifstream file(filename);
    
    string line;
    int n, m;
    vector<char> start_nodes;
    vector<char> end_nodes;
    
    file >> n >> m;
    file.ignore();
    
    getline(file, line);
    std::stringstream ss1(line);
    char node; 
    while (ss1 >> node) {
        start_nodes.push_back(node);
    }
    
    getline(file, line);
    std::istringstream ss2(line);
    while (ss2 >> node) {
        end_nodes.push_back(node);
    }

    vector<vector<vector<char>>> table(n, vector<vector<char>>(m)); // таблица переходов, строки - начальные вершины, столбцы - элементы алфавита, пересечения - состояния куда можно попасть
    vector<vector<char>> adjlist(n); // лист направлений для облегчения поиска
    
    string str;
    
    while (getline(file, line)) {
        if (line.empty()) continue;
        
        std::istringstream ss3(line);
        char start_char, symbol, end;
        if (ss3 >> start_char >> symbol >> end) {
            int state_ind = start_char - '0';
            int char_ind = symbol - '0';
            table[state_ind][char_ind].push_back(end);
            adjlist[state_ind].push_back(symbol);
        } else {
            break;
        }
    }
    str = line;
    file.close();

    bool flag = false;

    for(char state : start_nodes) {
        if(DFS(0, str, state, end_nodes, table, adjlist)) {
            flag = true;
            break;
        }
    }

    if(!flag) cout << "false";
    else cout << "true";
    
    return 0;
}