Pagini recente » Cod sursa (job #1363731) | Cod sursa (job #22166) | Cod sursa (job #2519807) | Cod sursa (job #2106085) | Cod sursa (job #2803271)
#include <bits/stdc++.h>
#define MaxP 1001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001],b[2000001];
int urmator[2000001],nrP;
vector<int> v;
void potrivire_naiva()
{
/// cautam a in sirul b
int n=strlen(a),m=strlen(b),i=0;
int j=0;
while(i<m)
{
if(a[j]!=b[i])
{
i-=j;
j=0;
}
else j++;
i++;
if(j==n)
{
///fout<<i-n<<" ";
nrP++;
if(nrP<MaxP)
v.push_back(i-n);
else
return;
i=i-n+1;
j=0;
}
}
}
void kmp()
{
/// cautam a in sirul b
// precalcul vector urmator
int n=strlen(a);
urmator[0]=-1;
int i=0,j=-1;
while(i<n)
{
while(j>=0&&a[i]!=a[j])
{
j=urmator[j];
}
i++;
j++;
urmator[i]=j;
}
//
int m=strlen(b);
i=0;
j=0;
while(i<m)
{
while(j>=0&&b[i]!=a[j])
j=urmator[j];
i++;j++;
if(j==n)
{
///fout<<i-n<<" ";
nrP++;
if(nrP<MaxP)
v.push_back(i-n);
else return;
}
}
}
int main()
{
fin.getline(a,sizeof(a));
fin.getline(b,sizeof(b));
potrivire_naiva();
//kmp();
fout<<v.size()<<'\n';
for(vector<int>::iterator it=v.begin();it!=v.end();it++)
fout<<*it<<" ";
}