Pagini recente » Istoria paginii runda/bruschete | Istoria paginii runda/please_d0_not_enter/clasament | Cod sursa (job #2159637) | Cod sursa (job #1040475) | Cod sursa (job #2426228)
#include <fstream>
#define MAX 2000001
using namespace std;
int lps[MAX], poz[MAX];
void preprocessing(string a)
{
int i, len, m;
len = 0;
lps[len] = 0;
i = 1;
m = a.length();
while(i < m)
{
if(a[i] == a[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if(len != 0)
{
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
int solve(string a, string b)
{
int matches = 0;
preprocessing(b);
int i, j, n, m;
i = j = 0;
n = a.length();
m = b.length();
while(i < n)
{
if(b[j] == a[i])
{
j++;
i++;
}
if(j == m)
{
poz[matches] = i - j;
matches++;
j = lps[m - 1];
}
else if(i < n && b[j] != a[i])
{
if(j != 0)
j = lps[j - 1];
else
i++;
}
}
return matches;
}
int main()
{
string a, b;
int matches, i;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> a >> b;
matches = solve(b, a);
fout << matches << '\n';
for(i = 0; i < matches; i++)fout << poz[i] << " ";
fin.close();
fout.close();
return 0;
}