Pagini recente » Cod sursa (job #1902729) | Cod sursa (job #1139651) | Cod sursa (job #2529996) | Cod sursa (job #570304) | Cod sursa (job #1122193)
// Include
#include <fstream>
using namespace std;
// Constante
const int sz = (int)2e6+2;
// Functii
void makePrefix();
// Variabile
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char str[sz], sub[sz];
int strLen, subLen;
int prefix[sz]; // prefix[i] este lungimea celui mai lung prefix al lui sub[1..i] care este si sufix al lui sub[1..i]
int answer, answers[1001];
// Main
int main()
{
in >> (sub+1) >> (str+1);
subLen = strlen(sub+1);
strLen = strlen(str+1);
// Formez vectorul prefix
makePrefix();
int currentPrefix = 0;
for(int i=1 ; i<=strLen ; ++i)
{
// Atat timp cat lungimea prefixului meu difera de 0, verific daca caracterul de pe pozitia i este
// acelasi cu cel de pe pozitia currentPrefix+1 (se stie ca, atat timp cat currentPrefix e diferit de 0
// primele currentPrefix caractere sunt egale)
while(currentPrefix && sub[currentPrefix+1] != str[i])
// Ma intorc la cel mai lung prefix-sufix al prefix-sufixului curent
currentPrefix = prefix[currentPrefix];
// Daca, crescand lungimea prefixului, voi gasi inca o potrivire, il cresc
if(sub[currentPrefix+1] == str[i])
++currentPrefix;
// Daca lungimea prefixului este egala cu lungimea subsirului, am gasit inca o potrivire
if(currentPrefix == subLen)
{
if(++answer <= 1000)
answers[answer] = i-subLen;
// Ma intorc la cel mai lung prefix-sufix al prefix-sufixului curent
currentPrefix = prefix[currentPrefix];
}
}
out << answer << '\n';
int limit = min(answer, 1000);
for(int i=1 ; i<=limit ; ++i)
out << answers[i] << ' ';
out << '\n';
in.close();
out.close();
return 0;
}
void makePrefix()
{
int currentPrefix = 0; // Valoarea pe care incerc s-o pun pe pozitia i
for(int i=2 ; i<=subLen ; ++i)
{
// Atat timp cat lungimea prefixului meu difera de 0, verific daca caracterul de pe pozitia i este
// acelasi cu cel de pe pozitia currentPrefix+1 (se stie ca, atat timp cat currentPrefix e diferit de 0
// primele currentPrefix caractere sunt egale)
while(currentPrefix && sub[currentPrefix+1] != sub[i])
// Ma intorc la cel mai lung prefix-sufix al prefix-sufixului curent
currentPrefix = prefix[currentPrefix];
// Daca, crescand lungimea prefixului, voi gasi inca o potrivire, il cresc
if(sub[currentPrefix+1] == sub[i])
++currentPrefix;
// Pun valoarea calculata pe pozitia i
prefix[i] = currentPrefix;
}
}