Pagini recente » Cod sursa (job #615929) | Cod sursa (job #2642068) | Cod sursa (job #395598) | Cod sursa (job #1332836) | Cod sursa (job #1092690)
// Include
#include <fstream>
#include <cstring>
using namespace std;
// Constante
const int sz = (int)2e6+1;
// Functii
void makePrefix();
// Variabile
ifstream in("kmp.in");
ofstream out("kmp.out");
char sub[sz], str[sz];
int subLen, strLen;
int prefix[sz];
int answer;
int answers[1001];
// Main
int main()
{
in >> (sub+1) >> (str+1);
subLen = strlen(sub+1);
strLen = strlen(str+1);
makePrefix();
int currentPrefix = 0;
for(int i=1 ; i<=strLen ; ++i)
{
while(currentPrefix && sub[currentPrefix+1] != str[i])
currentPrefix = prefix[currentPrefix];
if(sub[currentPrefix+1] == str[i])
{
if(++currentPrefix == subLen)
{
if(++answer <= 1000)
answers[answer] = i - subLen;
currentPrefix = prefix[currentPrefix];
}
}
}
out << answer << '\n';
int limit = min(1000, answer);
for(int i=1 ; i<=limit ; ++i)
out << answers[i] << ' ';
out << '\n';
in.close();
out.close();
return 0;
}
void makePrefix()
{
int currentPrefix = 0;
for(int i=2 ; i<=subLen ; ++i)
{
while(currentPrefix && sub[currentPrefix+1] != sub[i])
currentPrefix = prefix[currentPrefix];
if(sub[currentPrefix+1] == sub[i])
++currentPrefix;
prefix[i] = currentPrefix;
}
}