Pagini recente » Cod sursa (job #2634123) | Cod sursa (job #1408080) | Cod sursa (job #52233) | Cod sursa (job #1204305) | Cod sursa (job #1469507)
#include <fstream>
#include <vector>
#define LMAX 1000
#define NMAX 400001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int st,dr,pas;
int z[NMAX];
string A,B,S;
vector <int>sol;
int main()
{
f>>A>>B;
S=A+'$'+B;
int n=S.size()-1;
for (int i=1;i<=n;i++){
if (dr<i){
st=i;
for (dr=i;dr<=n && S[dr]==S[dr-st];dr++);
dr--;
z[i]=dr-st+1;
}
else {
int poz=i-st;
if (z[poz]+i<=dr)
z[i]=z[poz];
else {
for (st=i;dr<n && S[dr]==S[dr-st];dr++);
dr--;
z[i]=dr-st+1;
}
}
if (z[i]==A.size())sol.push_back(i-A.size()-1);
}
g<<sol.size()<<'\n';
for (auto it:sol)
{
if (++pas>LMAX)break;
g<<it<<" ";
}
}