Pagini recente » Cod sursa (job #2480196) | Cod sursa (job #902386) | Cod sursa (job #1734333) | Cod sursa (job #3142063) | Cod sursa (job #1631846)
#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[2000002];
char w[2000002],t[2000002];
vector<int> v;
int main()
{
fin>>w>>t;
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;
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=2;i<=m;i++)
{
if (k > 0 && w[k+1] != t[i])
k = pi[k];
if (w[k+1] == t[i])
k++;
if (k == n)
{
if (nr < 1000)
{
nr++;
v.push_back(i - n + 1);
}
}
}
fout<<nr<<"\n";
for (i=0;i<nr;i++)
fout<<v[i]<<" ";
return 0;
}