Pagini recente » Cod sursa (job #2893340) | Cod sursa (job #941627) | Cod sursa (job #1243754) | Cod sursa (job #2745940) | Cod sursa (job #1856240)
#include<fstream>
#include<vector>
#include<iostream>
#include<chrono>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
ifstream in("potrivire.in");
ofstream out("potrivire.out");
char s1[2000010];
char s2[2000010];
int prefix[2000010],nr=0;
vector<int> rez;
void make_prefix(char s[])
{
int l = strlen(s);
int i = 0, j = 1;
for (; j < l; ++j)
{
while (i > 0 && s[i] != s[j])
i = prefix[i - 1];
if (s[i] == s[j])
++i;
prefix[j] = i;
}
}
void KMP(char s1[], char sub[])
{
int l1 = strlen(s1);
int l2 = strlen(sub);
make_prefix(sub);
int i = 0, j = 0;
for (; j < l1;++j)
{
while (i > 0 && s1[j] != sub[i])
i = prefix[i - 1];
if (s1[j] == sub[i])
++i;
if (i == l2)
{
++nr;
if (nr <= 1000)
rez.push_back(j - i + 1);
}
}
}
int main()
{
in >> s1 >> s2;
KMP(s1, s2);
out << nr << "\n";
for (int i = 0; i < rez.size(); ++i)
out << rez[i] << " ";
return 0;
}