Pagini recente » Cod sursa (job #1639898) | Cod sursa (job #1030179) | Cod sursa (job #2393391) | Cod sursa (job #2599746) | Cod sursa (job #2366489)
#include<bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char txt[2000002],pre[2000002];
int l[2000002];
vector<int>ras;
void prefix()
{
int i=0;
int k=0;
for(int i=2;pre[i];++i)
{
while(k>0 && pre[k+1]!=pre[i])
k=l[k];
if(pre[k+1]==pre[i])
k++;
l[i]=k;
}
}
void potrivire()
{
int k=0;
for(int i=1;txt[i];++i)
{
while(k>0 && txt[i]!=pre[k+1])
k=l[k];
if(txt[i]==pre[k+1])
k++;
if(k==strlen(pre+1))
ras.push_back(i-k);
}
g<<ras.size()<<'\n';
for(auto it:ras)
g<<it<<' ';
}
int main()
{
f.get(pre+1,2000002);
f.get();
f.get(txt+1,2000002);
prefix();
potrivire();
}