Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"OOOVOOO","updateTime":1560484392000,"title":"挂了的单词","dislikeCnt":0,"content":"```\n#include\u003ciostream\u003e\n#include\u003ccstdio\u003e\n#include\u003cstring\u003e\n#include\u003ccstring\u003e\nusing namespace std;\nconst int maxn\u003d(int)1e6+50;\nint tree[maxn][26],fail[maxn],cnt[maxn],tot;\nint st[205];\nstring s;\nvoid insert(string st,int id)\n{\n\tint k\u003d0;\n\tfor(int q\u003d1;q\u003c\u003ds.length();q++)\n\t{\n\t\tif(!tree[k][s[q-1]-\u0027a\u0027])\n\t\t\ttree[k][s[q-1]-\u0027a\u0027]\u003d++tot;\n\t\tcnt[tree[k][s[q-1]-\u0027a\u0027]]\u003d1;\n\t}\n\tst[id]\u003dk;\n}\nint dui[maxn],l\u003d1,r;\ninline void getfail()\n{\n\tfor(int q\u003d0;q\u003c26;q++)\n\t{\n\t\tif(tree[0][q])\n\t\t{\n\t\t\tfail[tree[0][q]]\u003d0;\n\t\t\tdui[++r]\u003dtree[0][q];\n\t\t}\n\t}\n\twhile(r\u003e\u003dl)\n\t{\n\t\tint k\u003ddui[l++];\n\t\tfor(int q\u003d0;q\u003c26;q++)\n\t\t{\n\t\t\tif(tree[k][q])\n\t\t\t{\n\t\t\t\tfail[tree[k][q]]\u003dtree[fail[k]][q];\n\t\t\t\tdui[++r]\u003dtree[k][q];\n\t\t\t}\n\t\t\telse\n\t\t\t\ttree[k][q]\u003dtree[fail[k]][q];\n\t\t}\n\t}\n}\nint main()\n{\n\tint n;\n\tcin\u003e\u003en;\n\tfor(int q\u003d1;q\u003c\u003dn;q++)\n\t{\n\t\tcin\u003e\u003es;\n\t\tinsert(s,q);\n\t}\n\tgetfail();\n\tfor(int q\u003dl-1;q\u003e\u003d0;q--)\n\t\tcnt[fail[dui[q]]]+\u003dcnt[dui[q]];\n\tfor(int q\u003d1;q\u003c\u003dn;q++)\n\t\tcout\u003c\u003ccnt[st[q]]\u003c\u003cendl;\n}\n```","likeCnt":0,"createTime":1560484392000,"isWorkbook":false,"viewCnt":896,"openness":1,"fav":false,"id":1153,"trustable":false}