Pagini recente » Cod sursa (job #2892934) | Cod sursa (job #524585) | Cod sursa (job #2485620) | Cod sursa (job #1704206) | Cod sursa (job #671013)
Cod sursa(job #671013)
#include<stdio.h>
#include<assert.h>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string a,b;
int n,prefix[2001000];
vector <int> sol;
void read()
{
assert(freopen("strmatch.in","r",stdin)!=NULL);
cin >> a;
cin >> b;
}
void get_prefix()
{
prefix[0]=-1;
int i,j=0;
for(i=1;i<a.size();++i)
{
while(j!=-1)
{
if(a[i]==a[j])
{
prefix[i]=j;
++j;
break;
}
j=prefix[i-1];
}
if(j==-1)
{
j=0;
prefix[i]=-1;
}
}
}
void print_prefix()
{
int i;
for(i=0;i<a.size();++i)
printf("%d ",prefix[i]);
}
void find_matches()
{
int i,j=0;
for(i=0;i<b.size();++i)
{
while(j!=-1)
{
if(a[j]==b[i])
{
if(j==a.size()-1)
{
++n;
if(n<=1000)
sol.push_back(i);
j=prefix[j]+1;
}
else
{
++j;
}
break;
}
j=prefix[j];
}
if(j==-1)
j=0;
}
}
void solve()
{
get_prefix();
//print_prefix();
find_matches();
}
void write()
{
assert(freopen("strmatch.out","w",stdout)!=NULL);
int i;
printf("%d\n",n);
for(i=0;i<sol.size();++i)
printf("%d ",sol[i]-a.size()+1);
}
int main()
{
read();
solve();
write();
return 0;
}