Pagini recente » Cod sursa (job #863407) | Cod sursa (job #2768047) | Cod sursa (job #1685819) | Cod sursa (job #1616079) | Cod sursa (job #1046566)
#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>
#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)
#define INF 1000001
using namespace std;
#ifndef TEST
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#else
ifstream fin ("input.txt");
ofstream fout ("output.txt");
#endif
#define MAXN 2000000
string s,t;
vector<int> sol;
int T[MAXN+1];
void build()
{
int c = 0;
T[0] = -1;
T[1] = 0;
for (int i=2; i<s.length(); i++)
{
if (s[i-1]==s[c])
{
c++;
T[i]=c;
} else if (c>0)
{
c = T[c];
i--;
} else T[i]=0;
}
}
int main()
{
fin>>s>>t;
int sl,tl;
sl = s.length();
tl = t.length();
build();
int c=0,i=0;
while (i+sl <= tl)
{
if (t[i+c]==s[c])
{
if (c==sl-1)
{
sol.push_back(i);
i =i+c- T[c];
if (T[c]>-1)
c = T[c];
else c=0;
}
else c++;
} else
{
i = i+c -T[c];
if (T[c]>-1)
c = T[c];
else c=0;
}
}
fout<<sol.size();
fout<<'\n';
for (int i=0; i<min(sol.size(),1000); i++)
fout<<sol[i]<<' ';
return 0;
}