Pagini recente » Cod sursa (job #1859575) | Borderou de evaluare (job #2483990) | Cod sursa (job #1725862)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN = 2e6+5;
int v[MAXN];
string text, sablon;
vector <int> rez;
void prefix()
{
int i = 1, j = 0;
while(i < sablon.size())
{
if(sablon[i] == sablon[j])
v[i++] = ++j;
else
{
if(j!=0)
j = v[i-1];
else
i++;
}
}
}
void kmp()
{
int i = 0, j = 0;
while(i < text.size())
{
if(text[i] == sablon[j])
i++, j++;
else
{
if(j!=0)
j = v[j-1];
else
i++;
}
if(j == sablon.size())
rez.push_back(i-j);
}
}
int main()
{
fin>> sablon >> text;
prefix();
kmp();
fout<<rez.size() << endl;
for(auto it: rez)
if(it > 1000) exit(0);
else fout<<it << " ";
}