Pagini recente » Cod sursa (job #151875) | Cod sursa (job #1343278) | Cod sursa (job #2134135) | Cod sursa (job #1288955) | Cod sursa (job #2557679)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
vector<int>rez;
int pattern[200005];
int l;
char sir1[2000005], sir2[200005];
void create_pattern()
{
int j=1, i=0;
while(j<l)
{
if (sir1[i]==sir1[j])
{
pattern[j]=pattern[j-1]+1;
i++;
}
else
{
while(i!=0)
{
if(sir1[i]==sir1[j])
{
pattern[j]=i+1;
i++;
break;
}
else
i=pattern[i-1];
}
if(sir1[0]==sir1[j])
pattern[j]=1;
else
pattern[j]=0;
}
++j;
}
}
void parcurgere()
{
int l2=strlen(sir2);
int ind_pattern=0;
for (int i=0; i<l2; ++i)
{
if(sir2[i]==sir1[ind_pattern])
{
++ind_pattern;
if(ind_pattern==l)
{
rez.push_back(i-l+1);
ind_pattern=pattern[ind_pattern-1];
}
}
else
ind_pattern=pattern[ind_pattern];
}
}
int main()
{
f >> sir1 >> sir2;
l=strlen(sir1);
create_pattern();
parcurgere();
g << rez.size()<<'\n';
for (auto &v:rez)
g << v <<' ';
return 0;
}