Pagini recente » Monitorul de evaluare | Cod sursa (job #84056) | Cod sursa (job #1369107) | Cod sursa (job #3265089) | Cod sursa (job #2261187)
#include <bits/stdc++.h>
#define Petrisor void
#define MaxN 2000005
#define MaxA 1000
std::ifstream InFile("strmatch.in");
std::ofstream OutFile("strmatch.out");
// JESUS
// CHRIST
// WHAT IS WRONG WITH MY CODE FOR REAL NOW JESUUUUUS
// VREAU SA DOOOOORM
// Guess Ill sleep when I am dead <3
// SOMEBODY ONCE TOLD
// THE WORLD IS GONNA ROLL ME
// YOU KNOW, YOU WALK OUT THE DOOR. YOU SEE SOMEONE THAT YOU KNOW, AND THEY ASK YOU H O W Y O U A R E, AND YOU
// JUST HAVE TO SAY YOU ARE F I N E , WHEN YOU'RE NOT REALLY FINE, BUT YOU JUST CAN'T GET INTO IT
// BECAUSE THEY WOULD NEVER UNDERSTAND #EDGYNESS #BANDARIUS #AMUNPROFDECLASAINUTIL
char A[MaxN], B[MaxN]; // Sirurile citite (evident cu dimensiune foarte foarte foarte ok)
int M, N, NAns, // M - pt B, N - pt A (de parca conteaza); NAns - cate pozitii am gasit
LPS[MaxN]; // LPS[i] - poveste veche (A[0...i] lungime-1 a prefixului care e si sufix maxim)
std::vector <int> Ans; // Retinem pozitiile care trb asezate, pana in foarte clara valoare MaxA 1000
Petrisor PrecomputeLPS() {
int Len = 0; // LPS[1] = 0
for (int i=2; i<=N; ++i) {
while (Len && A[i] != A[Len+1]) // Nu e potrivit bine, dam skip
Len = LPS[Len];
if (A[Len+1] == A[i]) // Marim lungimea daca trb
++Len;
LPS[i] = Len;
}
}
Petrisor KMP() {
PrecomputeLPS();
int Len = 0;
for (int i=1; i<=M; ++i) {
while(Len && B[i] != A[Len+1]) // Nu e potrivit bine, dam skip
Len = LPS[Len];
if (A[Len+1] == B[i]) // Marim lungimea daca trb
++Len;
if (Len == N) {
NAns ++;
if (NAns <= MaxA)
Ans.push_back(i-N);
}
}
}
Petrisor Citire() {
InFile >> A+1 >> B+1;
N = strlen(A+1);
M = strlen(B+1);
}
Petrisor Rezolvare() {
KMP();
OutFile << NAns << '\n';
for (int i=0; i<Ans.size(); ++i)
OutFile << Ans[i] << ' ' ;
OutFile << '\n';
// Have mercy on me forever dear Gods up there
// Praise be.
}
int main()
{
Citire();
Rezolvare();
return 0;
}