Pagini recente » Cod sursa (job #493716) | Cod sursa (job #1324107) | Cod sursa (job #2243512) | Cod sursa (job #2329409) | Cod sursa (job #501392)
Cod sursa(job #501392)
#include<fstream>
#include<string.h>
#include<vector>
using namespace std;
#define pb push_back
vector <int> v;
vector <int> :: iterator it;
int pi[2000005];
char a[2000005],b[2000005];
int main()
{
int i,sw,n,m,cnt=0;
ifstream f("strmatch.in");
f>>a>>b;
n=strlen(a);
m=strlen(b);
pi[0]=0;
for (i=1;i<n;i++)
{
sw=pi[i-1];
while (sw>0 && a[i]!=a[sw])
sw=pi[sw-1];
if (a[i]==a[sw])
pi[i]=sw+1;
else
pi[i]=0;
}
sw=0;
for (i=0;i<m;i++)
{
while (sw>0 && b[i]!=a[sw])
sw=pi[sw-1];
if (b[i]==a[sw])
sw++;
if (sw==n)
{
++cnt;
sw=pi[sw-1];
if (cnt<=1000) v.pb(i+1-n) ;
}
}
ofstream g("strmatch.out");
g<<cnt<<'\n';
for (it=v.begin();it<v.end();++it)
g<<*it<<' ';
f.close();
g.close();
return 0;
}