请给出下面这段代码的时间复杂度分析： using namespace std; int n, maxn; string s, x, y; int front(int l) { int ans = 0; int k = 0; while(x[k] == 'w') { ans++; k++; } for(int i = k; i < n; i++) { if(x[k] == x[i] || x[i] =

该段代码中的时间复杂度为 O(n^2)，其中 n 是字符串 x 的长度。原因是代码中使用了两重循环，外层循环遍历字符串 x，内层循环从当前位置开始向右扩展，直到找到不同颜色的珠子为止。在最坏情况下，即字符串 x 全部为同一种颜色的珠子时，内层循环需要遍历整个字符串 x，因此总的时间复杂度为 O(n^2)。

相关问题

去掉注释：#include <iostream>#include <queue>#include <cstring>using namespace std;const int MAXN = 100005; // 最大字符串长度const int MAXM = 26; // 字符集大小struct AC_Automaton { int ch[MAXN][MAXM]; // Trie树 int val[MAXN]; // 节点值 int fail[MAXN]; // 失败指针 int tot; // 节点总数 void init() { memset(ch, 0, sizeof(ch)); memset(val, 0, sizeof(val)); memset(fail, 0, sizeof(fail)); tot = 0; } void insert(string s, int v) { // 插入字符串s，节点值为v int u = 0; for (int i = 0; i < s.size(); i++) { int c = s[i] - 'a'; if (!ch[u][c]) ch[u][c] = ++tot; u = ch[u][c]; } val[u] += v; } void build() { // 构建AC自动机 queue<int> q; for (int i = 0; i < MAXM; i++) { if (ch[0][i]) q.push(ch[0][i]); } while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < MAXM; i++) { if (ch[u][i]) { fail[ch[u][i]] = ch[fail[u]][i]; q.push(ch[u][i]); } else { ch[u][i] = ch[fail[u]][i]; } } val[u] += val[fail[u]]; // 合并节点值 } } int query(string s) { // 查询字符串s中出现的模式串的节点值之和 int u = 0, res = 0; for (int i = 0; i < s.size(); i++) { u = ch[u][s[i] - 'a']; res += val[u]; } return res; }} AC;int main() { AC.init(); int n; cin >> n; for (int i = 1; i <= n; i++) { string s; int v; cin >> s >> v; AC.insert(s, v); } AC.build(); string t; cin >> t; cout << AC.query(t) << endl; return 0;}

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 100005; // 最大字符串长度
const int MAXM = 26; // 字符集大小

struct AC_Automaton {
int ch[MAXN][MAXM]; // Trie树
int val[MAXN]; // 节点值
int fail[MAXN]; // 失败指针
int tot; // 节点总数

void init() {
memset(ch, 0, sizeof(ch));
memset(val, 0, sizeof(val));
memset(fail, 0, sizeof(fail));
tot = 0;
}

void insert(string s, int v) { // 插入字符串s，节点值为v
int u = 0;
for (int i = 0; i < s.size(); i++) {
int c = s[i] - 'a';
if (!ch[u][c]) ch[u][c] = ++tot;
u = ch[u][c];
}
val[u] += v;
}

void build() { // 构建AC自动机
queue<int> q;
for (int i = 0; i < MAXM; i++) {
if (ch[0][i]) q.push(ch[0][i]);
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < MAXM; i++) {
if (ch[u][i]) {
fail[ch[u][i]] = ch[fail[u]][i];
q.push(ch[u][i]);
} else {
ch[u][i] = ch[fail[u]][i];
}
}
val[u] += val[fail[u]]; // 合并节点值
}
}

int query(string s) { // 查询字符串s中出现的模式串的节点值之和
int u = 0, res = 0;
for (int i = 0; i < s.size(); i++) {
u = ch[u][s[i] - 'a'];
res += val[u];
}
return res;
}
} AC;

int main() {
AC.init();
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
string s;
int v;
cin >> s >> v;
AC.insert(s, v);
}
AC.build();
string t;
cin >> t;
cout << AC.query(t) << endl;
return 0;
}

#include <algorithm> #include <cstdio> #include <map> #include <queue> using namespace std; const int maxn = 205; const int INF = 0x3f3f3f3f; int d[maxn][maxn]; int terminal[maxn], vis[maxn][maxn]; map<int, int> been[maxn]; int n, m, k; int line[10000]; int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = (i == j) ? 0 : INF; int u, v, len; int fare; char ch; while (m--) { int len = 0; while (scanf("%d", &u)) { line[len++] = u; ch = getchar(); if (ch == '\n') { terminal[line[0]] = terminal[line[len - 1]] = 1; for (int i = 0; i != len - 1; i += 2) { u = line[i], v = line[i + 2]; d[v][u] = d[u][v] = min(d[u][v], line[i + 1]); } break; } } } for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j || d[i][j] == INF) continue; fare = 2 + d[i][j] / k; if (!been[i].count(fare) || been[i][fare] < d[i][j]) been[i][fare] = d[i][j]; } } int t, cur, first; queue<int> Q; scanf("%d", &t); while (t--) { first = 1; scanf("%d", &u); vis[u][u] = 1; Q.push(u); while (!Q.empty()) { cur = Q.front(); Q.pop(); for (int i = 1; i <= n; i++) { if (vis[u][i] || d[cur][i] == INF) continue; if (terminal[i]) { Q.push(i); vis[u][i] = 1; } else { fare = 2 + d[cur][i] / k; if (d[cur][i] == been[cur][fare]) { Q.push(i); vis[u][i] = 1; } } } } for (int i = 1; i <= n; i++) { if (vis[u][i]) { if (first) { printf("%d", i); first = 0; } else printf(" %d", i); } } printf("\n"); } return 0; }把这段代码改为C语言代码

下面是将该段代码改为C语言的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define maxn 205
#define INF INT_MAX

int d[maxn][maxn];
int terminal[maxn], vis[maxn][maxn];
int been[maxn][maxn];
int n, m, k;
int line[10000];

int main() {
    scanf("%d%d%d", &n, &m, &k);

    // 初始化距离矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = (i == j) ? 0 : INF;
        }
    }

    // 读入边并建图
    int u, v, len, fare;
    char ch;
    for (int i = 0; i < m; i++) {
        len = 0;
        while (scanf("%d", &u)) {
            line[len++] = u;
            ch = getchar();
            if (ch == '\n') {
                terminal[line[0]] = terminal[line[len - 1]] = 1;
                for (int i = 0; i != len - 1; i += 2) {
                    u = line[i], v = line[i + 2];
                    d[v][u] = d[u][v] = (d[u][v] > line[i + 1]) ? line[i + 1] : d[u][v];
                }
                break;
            }
        }
    }

    // Floyd算法求最短路
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][k] != INF && d[k][j] != INF && d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }

    // 记录每个站点到其他站点的最小票价
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j || d[i][j] == INF) {
                continue;
            }
            fare = 2 + d[i][j] / k;
            if (been[i][fare] < d[i][j]) {
                been[i][fare] = d[i][j];
            }
        }
    }

    // 处理查询
    int t, cur, first;
    scanf("%d", &t);
    while (t--) {
        first = 1;
        scanf("%d", &u);
        vis[u][u] = 1;
        for (int i = 1; i <= n; i++) {
            if (terminal[i]) {
                vis[u][i] = 1;
            } else {
                fare = 2 + d[u][i] / k;
                if (d[u][i] == been[i][fare]) {
                    vis[u][i] = 1;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (vis[u][i]) {
                if (first) {
                    printf("%d", i);
                    first = 0;
                } else {
                    printf(" %d", i);
                }
            }
        }
        printf("\n");
    }
    return 0;
}