Pagini recente » Borderou de evaluare (job #2201626) | Cod sursa (job #3233829) | Cod sursa (job #1726694) | Cod sursa (job #1725866)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN = 2e6+5;
int v[MAXN], nr;
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()){
nr++;
if(sablon.size() < 1000) rez.push_back(i-j);
}
}
}
int main()
{
fin>> sablon >> text;
prefix();
kmp();
fout<<nr << endl;
for(auto it: rez)
fout<<it << " ";
}