Pagini recente » Cod sursa (job #1112349) | Cod sursa (job #2677297) | Cod sursa (job #2948173) | Cod sursa (job #2726493) | Cod sursa (job #1147758)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char x[2000005],y[2000005];
int pi[2000005];
int d[2000005];
vector<int> sol;
int main()
{
fin.getline(x+1,2000002);
fin.getline(y+1,2000002);
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;
}