Pagini recente » Cod sursa (job #493068) | Cod sursa (job #1158094) | Cod sursa (job #2161010) | Cod sursa (job #1373934)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int pi[2000001];
int n,m;
vector <int>sol;
void prefix(char a[])
{
int k=0;
pi[1]=0;
for(int i=2; i<=m; i++)
{
while(k>0 && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i])
k++;
pi[i]=k;
}
}
int ct;
void solve(char a[],char b[])
{
prefix(a);
int k=0;
for(int i=1; i<=n; i++)
{
while(k>0 && a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i])
k++;
if(k==m)
{
k=pi[m];
ct++;
if(ct<=1000)
sol.push_back(i-m);
}
}
g<<ct<<"\n";
ct=min(ct,1000);
for(int i=0; i<ct; i++)
g<<sol.at(i)<<" ";
}
int main()
{
char a[2000005],b[2000005];
f>>a;
f.get();
f>>b;
f.close();
int i;
for (i = 0; a[i] >= '0' && a[i] <= 'z'; ++i);
m = i;
for (i = 0; b[i] >= '0' && b[i] <='z'; ++i);
n = i;
for (i = m; i >= 1; --i)
a[i] = a[i-1];
a[0] = ' ';
for (i = n; i >= 1; --i)
b[i] = b[i-1];
b[0] = ' ';
solve(a,b);
}