Pagini recente » Cod sursa (job #756198) | Cod sursa (job #1786259) | Cod sursa (job #378521) | Cod sursa (job #2675828) | Cod sursa (job #1147755)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char x[2000001],y[2000001];
int pi[2000001];
int d[2000001];
vector<int> sol;
int main()
{
fin.getline(x+1,2000000);
fin.getline(y+1,2000000);
int n = strlen(x+1);
int m = strlen(y+1);
int k = 0;
pi[1] = 0;
for(int i=2;i<=n;i++)
{
while(k && x[i] != x[k+1])
k = pi[k];
if(x[k+1] == x[i])
++k;
pi[i] = k;
}
k = 0;
for(int i=1;i<m;i++)
{
while(k && y[i] != x[k+1])
k = pi[k];
if(y[i] == x[k+1])
++k;
d[i] = k;
if(d[i] == n)
sol.push_back(i-n);
}
fout<<sol.size()<<'\n';
for(unsigned int i=0; i<sol.size() && i<1000;i++)
fout<<sol[i]<<' ';
fin.close();
fout.close();
return 0;
}