Pagini recente » Cod sursa (job #285283) | Cod sursa (job #682946) | Cod sursa (job #2560881) | Cod sursa (job #2381373) | Cod sursa (job #2734351)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,pi[2000005],nr=0;
string a,b;
vector<int> sol;
void make_prefix()
{
int poz=0;
pi[1]=0;
for(int i=2; i<=n; i++)
{
while( poz!=0&&a[poz+1]!=a[i] )
poz=pi[poz];
if( a[poz+1]==a[i] ) poz++;
pi[i]=poz;
}
}
int main()
{
f>>a>>b;
n=a.length();
m=b.length();
a=" "+a;
b=" "+b;
make_prefix();
int poz=0;
for(int i=1; i<=m; i++)
{
while( poz!=0&&a[poz+1]!=b[i] )
poz=pi[poz];
if( a[poz+1]==b[i] ) poz++;
if(poz==n)
{
poz=pi[poz];
nr++;
if( nr<=1000 ) sol.push_back(i-n);
}
}
g<<nr<<'\n';
for(int i=0; i<sol.size(); i++) g<<sol[i]<<' ';
}