Pagini recente » Cod sursa (job #544144) | Cod sursa (job #2831154) | Cod sursa (job #385947) | Cod sursa (job #2059662) | Cod sursa (job #3196436)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s[2000001], s2[2000001]; short v[2000001];
int v2[100000];
int main()
{
int n, m, z = 0;
v[0] = 0;
fin.get(s,2000000);
fin.get();
fin.get(s2,2000000);
//cout << s;
//cout << s2;
n = strlen(s2);
m = strlen(s);
for(int i = 1; i < m; i++)
{
if(v[i-1] != 0)
{
if(s[v[i-1]] == s[i])
{
v[i] = v[i-1] + 1;
}
else v[i] = 0;
}
else
{
if(s[i] == s[0]) v[i] = 1;
else v[i] = 0;
//cout << s[i] << ' ' << s[0] << v[i];
}
}
int i = 0;
int j = 0;
while(i < n)
{
if(s[j] == s2[i])
{
i++;
j++;
}
if(j == m)
{
v2[++z] = i - m;
j = v[j-1];
}
else if(i < n && s[j] != s2[i])
{
if(j != 0)
{
j = v[j-1];
}
else i++;
}
}
fout << z << endl;
for(int i = 1; i <= z; i++)
fout << v2[i] << ' ';
/*
for(int i = 0; i < m; i++)
{
cout << v[i];
}*/
return 0;
}