Pagini recente » Cod sursa (job #1032524) | Cod sursa (job #574031) | Cod sursa (job #2732765) | Cod sursa (job #2520425) | Cod sursa (job #3040204)
///infoarena Potrivirea sirurilor
#include <fstream>
#include <vector>
#define SMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[SMAX], b[SMAX];
int lps[SMAX];
int k;
vector<int> rez;
int i;
int main()
{
fin >>a>>b;
k = -1; lps[0] = 0;
for (i = 1; a[i]; ++i)
{
while (k > 0 && a[k+1] != a[i]) k = lps[k];
if (a[k+1] == a[i]) k++;
lps[i] = k;
}
k = -1;
for (i = 0; b[i]; ++i)
{
while (k > 0 && a[k+1] != b[i]) k = lps[k];
if (a[k+1] == b[i]) k++;
if (!a[k+1])
{
rez.push_back(i-k);
k = lps[k];
}
}
fout <<min((int)rez.size(), 1000)<<'\n';
for (i = 0; i < min((int)rez.size(), 1000); ++i)
fout <<rez[i]<<' ';
fout <<'\n';
fout.close();
return 0;
}