Pagini recente » Cod sursa (job #1412200) | Cod sursa (job #209131) | Cod sursa (job #2681013) | Cod sursa (job #2539697) | Cod sursa (job #1634371)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,i,k,nr;
int pi[2000010];
char w[2000010],t[2000010];
vector<int> v;
int main()
{
fin.get(w, 2000010);
fin.get();
fin.get(t, 2000010);
n = strlen(w);
m = strlen(t);
for (i=n;i>=1;i--)
w[i] = w[i-1];
w[0] = 0;
for (i=m;i>=1;i--)
t[i] = t[i-1];
t[0] = 0;
pi[1] = 0;
k = 0;
for (i=2;i<=n;i++)
{
if (k > 0 && w[k+1] != w[i])
k = pi[k];
if (w[k+1] == w[i])
k++;
pi[i] = k;
}
k = 0;
for (i=1;i<=m;i++)
{
if (k > 0 && w[k+1] != t[i])
k = pi[k];
if (w[k+1] == t[i])
k++;
if (k == n)
{
nr++;
if (nr <= 1000)
v.push_back(i - n);
}
}
fout<<nr<<"\n";
for (i=0;i<min(1000,nr);i++)
fout<<v[i]<<" ";
return 0;
}